KMP（2）

求 next 数组（暴力版本）

Next[0] = -1
Next[1] = 0
For i = 2...P.len
    Next[i] = 0;
    For j = i - 1...1
        If P[1...j] == P[i - j + 1...i]//P[1...j]是P[1...i]的后缀
            Next[i] = j
            Break

不过上面这个根据定义直接求的算法时间复杂度太高了。如果不优化会成为整个 KMP 的瓶颈，导致还不如直接用 O (P.len * S.len) 的暴力算法匹配效率高。要优化求 next 数组的算法，就需要对 next 数组有深入的理解。首先要理解，next 实际上描述了 P 的所有前缀字符串两两之间的一种关系

举个例子，P=”bababb”，则 P 一共有 6 个前缀，依次是”b”,“ba”, “bab”, “baba”, “babab”, “bababb”。在这 6 个字符串中，如果 P [1..k] 恰好是 P [1..j] 的后缀，我们就连一条从 P [1..j] 到 P [1..k] 的虚线，表明这种后缀关系。显然这种后缀关系是一个偏序关系，也就是说如果 P [1..i] 是 P [1..k] 的后缀，而 P [1..k] 是 P [1..j] 的后缀，那么 P [1..i] 一定也是 P [1..j] 的后缀

比如上图中 P [1..1]（”b”）是 P [1..3]（”bab”）的后缀，P [1..3]（”bab”）是 P [1..5]（”babab”）的后缀。所以 P [1..1] （”b”）也是 P [1..5] （”babab”）的后缀。特别的，如果 P [1..k] 是 P [1..j] 最长的后缀，我们就连一条从 P [1..j] 到 P [1..k] 的实线，表明这种最长后缀关系

这个实线表明的” 最长后缀关系 “，实际上就是 next 数组。比如 P [1..6] 指向 P [1] 对应 next [6]=1；P [1..5] 指向 P [1..3] 对应 next [5]=3。而且如果我们想知道都有哪些前缀是 P [1..j] 的后缀，只需要沿着实线也就是 next 数组往上找即可：P [1..next [j]], P [1..next [next [j]]], P [1..next [next [next [j]]]], … Ø。此外，如果 P [1..k] 是 P [1..j] 的后缀，那么各自砍掉最后一个字母后，P [1..k-1] 仍是 P [1..j-1] 的后缀

有了以上两条分析结果，我们就可以来求 next 数组了。首先令 next [0]=-1, next [1]=0。然后我们用递推法依次求出每一个 next [j]。假设我们已经求出来 next [0], next [1], … next [j]，现在要求 next [j+1]

假设 next [j+1] 的值是 k，那么 P [1..k] 就必须是 P [1..j+1] 的后缀，所以 P [1..k-1] 就必须是 P [1..j] 的后缀（都砍掉最后一个字符）。而之前我们分析得出 P [1..j] 的后缀分别是 P [1..next [j]]， P [1..next [next [j]]], P [1..next [next [next [j]]]], … Ø；所以如果 next [j+1] 不等于 0 的话，next [j+1] 就只可能是 next [j]+1 或者 next [next [j]]+1 或者 next [next [next [j]]]+1… 或者 1

而我们要求 next [j+1]，就要在集合 { next [j]+1，next [next [j]]+1，next [next [next [j]]]+1，…… 1} 中找到一个最大的数 k，满足 P [k]==P [j+1]。如果这样的 k 存在，那么 next [j+1]=k；否则 next [j+1]=0

j = Next[0] = -1
For i = 1...P.len
    While j >= 0 AND P[j + 1] != P[j]
        j = next[j]
    Next[i] = ++j

下面看一下 KMP 求匹配的完整代码：

#include <cstring>
#include <cstdio>
using namespace std;
int next[1000001];
int ans;
char p[1000001],s[1000001];
int n,m;
int main()
{
    ans = 0;
    scanf("%S%S",p + 1,s + 1);
    n = strlen(s + 1);
    m = strlen(p + 1);
    next[0] = -1;
    int j = -1;
    for(int i = 1;i <= m;i++)
    {
        while(j >= 0 && p[j + 1] != p[i])
            j = next[j];
        next[i] = ++j;
    }
    j = 0;
    for(int i = 1;i <= n;i++)
    {
        while(j >= 0 && p[j + 1] != s[i])
            j = next[j];
        ++j;
        if(j == m)
        {
            ans = i - m + 1;
            break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

首先要注意上面代码中字符串都是从 P [1] 和 S [1] 开始的，并不是从下标 0 开始。并且 n 和 m 分别是 S 的长度和 P 的长度。第 16-21 行是在求 next 数组。第 23-33 行是在进行 KMP 匹配。注意其中第 28-32 行，如果匹配已经进行到 j==m，说明 P 的最后一个字符 P [m] 也匹配上了，并且匹配到的是 S [i]。这里我们是要在 S 中找 P 第一次出现的位置，也就是 P [1] 的位置，所以是 i-m+1

例 1 题目链接：hihoCoder1015

这道题的大意是给你很多对模式串 P 和原串 S。对于每一对都让你求出 P 在 S 中出现了多少次。需要注意出现的 P 是可以部分重叠的，比如 ADA 在 ADADADA 中出现了 3 次

之前 KMP 的代码是找到第一次出现的位置就中止了。现在我们需要让 KMP 在找到一次完整的匹配之后还能继续匹配下去。让匹配继续进行的方法就是，当 P [m] 匹配 S [i] 成功时，（这里 m 是 P 的长度）令 j=next [m]，然后从尝试 S [i+1] 和 P [j+1] 匹配继续
以下是完整的代码：

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int nxt[1000001];
int ans,t;
char p[1000001],s[1000001];
int n,m;
int main()
{
    cin >> t;
    while(t--)
    {
        ans = 0;
        scanf("%s%s",p + 1,s + 1);
        n = strlen(s + 1);
        m = strlen(p + 1);
        nxt[0] = -1;
        int j = -1;
        for(int i = 1;i <= m;i++)
        {
            while(j >= 0 && p[j + 1] != p[i])
                j = nxt[j];
            nxt[i] = ++j;
        }
        j = 0;
        for(int i = 1;i <= n;i++)
        {
            while(j >= 0 && p[j + 1] != s[i])
                j = nxt[j];
            if(++j == m)
            {
                ans++;
                j = nxt[j];
            }
        }
        cout << ans << endl;
    }
    return 0;
}

首先是 c++11 中 std::next 是有定义的，所以为了提交到 hihoCoder 上不会编译出错，我们把 next [] 数组的名字改成 nxt []。然后就是第 31-35 行，这里匹配到 j==m 说明完成了一个完整匹配之后，我们令 j=nxt [j]，就可以让 KMP 继续找下一个完整匹配的位置。最后 ans 的值就是答案