跳转至

KMP 匹配

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

border

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

性质：

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

nxt 数组

nxt[i] 表示字符串 \(s\) 长度为 \(i\) 的前缀的最长 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;
}

这段代码中，\(j\) 记录 border 长度，要么增加 \(1\)，要么向回跳。

我们为了保证 nxt 数组不统计到 \([0,i]\) 前缀本身，即 nxt[i]\(\leq i\)（因为 \([0,i]\) 一共 \(i+1\) 的长度），注意到每次循环，\(i\) 和 \(j\) 的间距要么不变，要么拉大。所以我们将 \(i\) 从 \(1\) 开始循环，保证 nxt[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];
    }
}

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