KMP算法

KMP算法通常应用于字符串匹配之类的问题中，它与暴力匹配的不同之处在于巧妙的消除了匹配的指针的回溯问题。使得问题的复杂度从$O(nm)$下降到了$O(n+m)$。

在KMP算法之中，巧妙的应用了Next数组，当第i位匹配不成功时，下次匹配直接比较Next[i]的位置。其中，next[i]的值表示P[0…i-1]中最长后缀的长度等于相同字符序列的前缀。

Next数组代码实现如下：

const int N = 1e5 + 10;
int Next[N];

void kmp_pre(char s[], int m) 
{
    int i, j;
    i = 0;
    j = Next[0] = -1;
    while (i < m) {
        while (j != -1 && s[i] != s[j]) j = Next[j];
        if (s[++i] == s[++j]) Next[i] = Next[j];
        else Next[i] = j;
    }
}

使用KMP算法查找x在y中出现的次数：

int kmp(char x[], int m, char y[], int n)
{
    int i, j, ans = 0;
    i = j = 0;
    while (i < n) {
        while (j != -1 && y[i] != x[j]) j = Next[j];
        i++, j++;
        if (j >= m) {
            ans++;
            j = Next[j];
        }
    }
    return ans;
}

Next数组除字符串匹配之外，还能判断一个字符串最多是由多少个相同不重叠子串构成。
当我们发现i-Next[i]能够整除i时候,那么s[1~i-Next[i]]就是s[i-1]的最小循环元,至于次数那么也就是i/(i-Next[i])。 证明略。

附加KMP算法的练习题：https://cn.vjudge.net/contest/310754