题解 | #kmp算法#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        // write code here
        int count = 0;
        int next[S.size()];//结果和next数组，next[x]的意义是长度为x的前子串最长相同前后缀长度
        int j = 0;//j:前缀起始位置, i: 后缀起始位置
        next[0] = 0;
        for(int i = 1; i < S.size(); i++){
            while(j > 0 && S[i] != S[j]){// j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j-1];//前缀和后缀不相等,找上一次最长前后缀对应的位置回退
            }
            if(S[i] == S[j]) j++;//前缀后缀相等,i,j均后移一位
            next[i] = j;//最长前后缀长度
        }
        j = 0;
        for(int i = 0; i < T.size(); i++){
            while(j > 0 && T[i] != S[j]){
                j = next[j-1];//如果不匹配,回到前缀表上一个位置对应的位置重新匹配
            }
            if(T[i] == S[j]){
                j++;
            }
            if(j == S.size()){
                count++;
                j = next[j-1];
            }
        }
        return count;
    }
};