KMP 匹配
KMP 算法可以在线性时间复杂度内解决字符串匹配问题和字符串前缀 border 问题。
border
若 \(s\) 的一个子串既是它的前缀又是它的后缀,则这个子串是它的一个 border
(一般不包含本身)。
性质:
border
的border
还是border
。- 两个不等的
border
一定是border
关系。
nxt 数组
nxt[i]
表示字符串 \(s\) 长度为 \(i\) 的前缀的最长 border。
这段代码中,\(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
树的子树大小,就是每个前缀在原串中出现的总次数。
KMP 匹配过程
\(i\) 是指向 \(s\) 的指针,\(j\) 是指向 \(t\) 的指针。随着 \(i\) 的推进,若 \(s[i] = t[j]\) 则 \(j\) 也推进,反之 \(j\) 回退到 \(nxt[j]\)。思路和求 nxt
很相似。