题解 | #kmp算法#

在Carl那学的KMP算法

class Solution {
public:
    int kmp(string S, string T) {
        int ans = 0;
        int next[S.size()];
        int j = 0;
        next[0] = 0;
        for(int i = 1;i < S.size();i++)
        {
            while(j > 0 && S[i] != S[j])
                j = next[j - 1];
            if(S[i] == S[j])
                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())
            {
                ans++;
                j = next[j - 1];
            }
        }
        return ans;
    }
};