题解 | #kmp算法#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        // write code here
        int count = 0;
        int i = 0;
        int j = 0;
        int [] next = getNext(S);
        while(i<T.length()&&j<S.length()){
            if(j==-1||T.charAt(i)==S.charAt(j)){
                i++;
                j++;
            }else{
                j = next[j];
            }
            if(j == S.length()){
                count++;
                j = next[j-1]+1;
            }

        }
         return count;
    }

     public int[] getNext(String s){
        int i = 0;
        int j = -1;
        int [] next = new int[s.length()];
        next[0] = j;
        while(i<s.length()-1){
              if(j==-1||s.charAt(i)==s.charAt(j)){
                j++;
                i++;
                next[i] = j;
              }else{
                j = next[j];
              }
        }
        return  next;
     }


}

此题是原生KMP算法的变种版，原生KMP算法在于匹配成功后，返回主串当中的起始下标。

这道题的要求是，子串在主串中出现的次数？

原理不变，解法在于：当我们匹配成功后，count++，并且j回溯到j=[j-1]，还要将结果再+1，为什么要加1，根据next数组的计算，j值的计算等于前缀/后缀长度+1，那么当j回溯到前一个j-1，再求当前j的值就要+1