kmp算法原理

kmp是一种快速匹配字符串的算法。它的核心是Next[]数组。
模板：母串t，子串s，求s在t中出现的次数以及出现的位置。
在朴素算法中，每一次匹配到一个子串或失配时，都会返回到开始匹配的字符的下一位在重新匹配，时间复杂度O(|st|)，明显太慢了。而kmp算法可以将时间复杂度缩小为O(s+t)。
Next[]数组的长度与子串s相同，其中，Next[i]表示s的前i个字符里，前缀与后缀相同的最大长度(前后缀不能包含全部字符)，例如
"abcabc"，这个子串中，Next[]数组的值依次为:0,0,0,1,2,3.
这个Next[]数组功能很强大，务必要彻底理解，并能用于任何需要的地方。
Next[]数组求取

void GetNext(char *s,int len,int Next[]){
    for (int i=2,j=0;i<=len;i++){
        while (j && s[i]!=s[j+1])   j=Next[j];
        if (s[i]==s[j+1])   j++;
        Next[i] = j;
    }
    return;
}

下面来解释求取的过程。
在每一次循环开始之前，i=i，表示要求的Next的下标，j=Next[i-1],即前i-1个字符的最优解，那么这两个之间有什么关系呢？很明显，Next[i]的值最大为Next[i-1]+1,在s[i]==s[j+1]的情况下。那么当二者不等时，即失配了，j要赋值为Next[j]，继续判断，直至j为0.这样的话这个函数就很容易理解了。这种求法可以保证解为最优。

有了Next数组，那么这个问题就很容易求解了，直接遍历一次母串即可。
i表示当前扫描母串t的下标，j表示当前扫描子串s的下标。当匹配时，j++,i++;当失配时，j=Next[j]，继续匹配。

for (int i=1,j=0;i<=len1;i++){
    while (j && t[i]!=s[j+1])   j=Next[j];
    if (t[i]==s[j+1])   j++;
    if (j==len2){
        opera();     //找到一次出现次数后的相关操作。
        j=Next[j];
    }
}