题解 | #kmp算法#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    int kmp(string S, string T) {
        int next[S.length()],sum=0;
        next[0]=0;
        for(int i=1,j=0; i<S.length(); )
        {
            if(S[i]==S[j])
                next[i++]=++j;
            else if(j)
                j=next[j-1];
            else
                next[i++]=0;
        }
        for(int i=0,j=0; j<T.length(); )
        {
            if(S[i]==T[j])
            {
                i++,j++;
                if(i==S.length())
                {
                    i=next[i-1];
                    sum++;
                }
            }
            else if(i)
                i=next[i-1];
            else
                j++;
        }
        return sum;
    }
};

KMP算法：算特征数组：abcadabcab
0001012342