题解 | #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){
            next[0]=0;
            int i=1;
            int len=0;
            while (i<size) {
                if(s[len]==s[i]){
                    len++;
                    next[i]=len;
                    i++;
                }else{
                    if(len>0){
                        len=next[len-1];
                    }else{
                        next[i]=0;
                        i++;
                    }
                }
            }
        return;
    }
    void move_next(vector<int> &next){
        for(int i=next.size()-1;i>0;i--){
            next[i]=next[i-1];
        }
        next[0]=-1;
    }
    int kmp(string S, string T) {
        // write code hereS
        unsigned int size_S=S.size();
        unsigned int size_T=T.size();
        vector<int> next;
        int result =0;
        next.resize(size_S,0);
        compute_next(S, next, S.size());
        move_next(next);

        int i=0;
        int j=0;
        while(i<size_T){
            if(S[j]==T[i]){
                i++;
                j++;
            }else{
                j=next[j];
                if(j<0){
                    j=0;
                    i++;
                }
            }

            if(j==size_S-1 && S[j]==T[i]){
                result++;
                j=next[j];
            }
        }
       
       

        return result;
    }
};