跳转至

KMP 匹配

KMP 算法可以在线性时间复杂度内解决字符串匹配问题和字符串前缀 border 问题。

border

若 ss 的一个子串既是它的前缀又是它的后缀，则这个子串是它的一个 border（一般不包含本身）。

性质：

  • border 的 border 还是 border。
  • 两个不等的 border 一定是 border 关系。

nxt 数组

nxt[i] 表示字符串 ss 长度为 ii 的前缀的最长 border。

1
2
3
4
5
for(int i = 1, j = 0; i < s.size(); i++) {
    while(j > 0 && s[i] != s[j]) j = nxt[j - 1];
    if(s[i] == s[j]) j++;
    nxt[i] = j;
}

这段代码中，jj 记录 border 长度，要么增加 11，要么向回跳。

我们为了保证 nxt 数组不统计到 [0,i][0,i] 前缀本身，即 nxt[i]≤i\leq i（因为 [0,i][0,i] 一共 i+1i+1 的长度），注意到每次循环，ii 和 jj 的间距要么不变，要么拉大。所以我们将 ii 从 11 开始循环，保证 nxt[i]≤i\leq i。

nxt 树

我们将每个节点的 nxt 作为它的 fa，会形成一棵树。一个节点的所有祖先代表该前缀的所有 border。我们可以使用这种方法计数每一个前缀作为 border 出现了多少次。容易发现，该前缀作为 border 出现的次数，就是在原字符串中出现的次数。因此直接统计 nxt 树的子树大小，就是每个前缀在原串中出现的总次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
cin >> s;
n = s.size();

for(int i = 1, j = 0; i <= n; i++) {
    while(j && s[j] != s[i]) j = nxt[j - 1];
    if(s[i] == s[j]) ++j;
    nxt[i] = j;
}

for(int i = n - 1; i > 0; i--) {
    f[i]++;
    f[nxt[i] - 1] += f[i];
}
f[0]++;

KMP 匹配过程

1
2
3
4
5
6
7
8
for(int i = 0, j = 0; i < s.size(); i++) {
    while(s[i] != t[j]) j = nxt[j - 1];
    if(s[i] == t[j]) j++;
    if(j == t.size()) {
        ans++;
        j = nxt[j - 1];
    }
}

ii 是指向 ss 的指针，jj 是指向 tt 的指针。随着 ii 的推进，若 s[i]=t[j]s[i] = t[j] 则 jj 也推进，反之 jj 回退到 nxt[j]nxt[j]。思路和求 nxt 很相似。