题解 | #kmp算法#

#include <cstdio>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    void compute_next(string s,vector<int> &next,int size){
        int j=0;
        int i=1;
        while(i<size){
            if(j==0 || s[i]==s[j]){
                next[++i]=++j;
                //cout<<next.size()<<" "<<i<<endl;
            }else{
                j=next[j];
            }
        }
        return;
    }
    int kmp(string S, string T) {
        // write code hereS
        unsigned int size_S=S.size();
        unsigned int size_T=T.size();
        vector<int> next;
        //cout<<size_S<<endl;
        next.resize(size_S+1,0);
        compute_next(S, next, S.size());
        //cout<<next[size_s]<<endl;
        int i=0;
        int j=0;
        int result=0;

        while(i<size_T){

            if(j==0 || S[j] == T[i]){
                j++;
                i++;
            }else{
                
                j=next[j];
            }
            if(j==size_S){
                result++;
                j=next[j];

            }
        }

        return result;
    }
};