题解 | #kmp算法#

class Solution {
public:
    int kmp(string S, string T) {
        int res = 0;
        int len = T.size();
        int next[len];
        getNext(next, S);

        // 遍历模板串T 看和文本串S 相等的长度是否等于S的长度
        int j=0;
        for(int i=0; i<T.size(); i++) {
            while(j>0 && S[j]!=T[i])
                j = next[j-1];
            if(S[j] == T[i])
                j++;
            // j的大小即为KMP匹配的长度，与 S的长度相等即为匹配上了
            if(j == S.size())
                res ++;
        }

        return res;
    }

    // 构造 Next数组
    void getNext(int* next, const string& s) {
        int j=0;
        next[0] = j;
        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;
        }
    }
};