跳转至

KMP 匹配

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

border

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

性质:

  • borderborder 还是 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 树的子树大小,就是每个前缀在原串中出现的总次数。

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 很相似。