题解 | KMP算法

int kmp(string S, string T) {
    // write code here

    int n = S.length();
    int m = T.length();
    int N = 5e5+10;
    int ne[N];
    int cnt=0;
    ne[0] = 0;
    //ne数组求解
    for(int i=1, j=0; i<n; i++)
    {
        while(j && S[j]!=S[i])    j = ne[j-1];
        if(S[j]==S[i])    j++;
        ne[i]=j;
    }

    //匹配模板链
    for(int i=0, j=0; i<=m; i++)
    {
        while(j && S[j]!=T[i])    j = ne[j-1];
        if(S[j]==T[i])    j++;
        if(j==n)
        {
            cnt++;
            j = ne[j-1];
        }
    }
    return cnt;