题解 | #kmp算法#

//时间复杂度O(m+n)，对解题思路感兴趣的朋友可以查看我的专栏"KMP算法的数学原理（优化版）"
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    void compute_next(string_view s,int *next){
        int m=s.size(),k=0;
        next[0]=0;
        for(int i=1;i<m;++i){
            next[i]=k;
            while(k>0 && s[i]!=s[k]){
                k=next[k];
            }
            if(s[i]==s[k])
                ++k;
        }
    }
    int kmp(string S, string T) {
        int m=S.size();
        int n=T.size();
        int next[m];
        compute_next(S, next);
        int count{0};
        for(int i=0,j=0;j<n;++j){
            while(i>0 && S[i]!=T[j]){
                i=next[i];
            }
            if(S[i]==T[j]){
                ++i;
            }
            if(i==m){
                while(i>0){
                    i=next[i-1];
                    if(S[i]==T[j]){
                        ++i;
                        break;
                    }
                }
                ++count;
            }
        }
        return count;
    }
};