题解 | #KMP#

class Solution {
public:
    vector<int> getNext(string pattern){
        int n = pattern.length();
        vector<int> next(n, 0);
        int j = next[0] = -1;
        for(int i = 1; i < n; i ++){
            while(j != -1 && pattern[i] != pattern[j + 1]) j = next[j]; //回退
            if(pattern[i] == pattern[j + 1]) j ++;
            next[i] = j;
        }
        return next;
    }
    int kmp(string S, string T) {
        // write code here
        vector<int> next = getNext(S);
        int m = T.length(), n = S.length();
        int j = -1;
        int ans = 0;
        for(int i = 0; i < m; i ++){
            while(j != -1 && T[i] != S[j + 1]) j = next[j];
            if(T[i] == S[j + 1]) j ++;
            if(j == n - 1){
                ans ++;
                j = next[j];
            }
        }
        return ans;
    }
};