声明：本文整理了北大附中肖然老师关于KMP讲解的核心要点。
符号
- 子串：从原串中选取连续的一段，即为子串；空串也是子串
- 前缀：pre(s, k) 为 s 前 k 个字符构成的子串
- 后缀：suf(s, k) 为 s 后 k 个字符构成的子串
- 任何子串都是某个后缀的前缀
- 最长公共前缀 lcp(s, t)：找出 s 和 t 最长的相同的前缀
- 最长公共后缀 lcs(s, t)
- 周期 （Period）：
- \(0 < p < |S|\)
- \(s[i] = s[i + p], \forall i \in \{1,2,\dots,|s|-p\}\)
- 满足以上条件，称 p 为 s 的周期
- Border
- \(0 < r < |S|\)
- pre(s, r) = suf(s, r)
- 满足以上条件，称 pre(s, r) 是 s 的 border
- 周期与Border：pre(s, k)是 s 的 border 等价于 |s| - k 是 s 的周期
Border 的传递性
- 串 s 是 t 的 border，串 t 是 r 的 border，那么 s 是 r 的border。
- 串 s 是 r 的 border，串 t （|t| > |s|）也是 r 的 border，那么 s 是 t 的 border。
- 记 mb(s) 表示 s 的最长 border
- 则 mb(s), mb(mb(s)), ... 构成了 s 的所有 border
- s 的所有 border 环环相扣，被 1 条链串起来
KMP 策略
调整 j 的位置（减小 j）使得性质“suf(pre(t, i), j) = pre(s, j)”。其中 t 为原串，s 为模式串。
next数组
- next[j] = pre(s, j)的最长 border 长度 = mb(pre(s, j))
- pre(s, j - 1)的所有 border 其实就是 next[j - 1], next[next[j - 1]], ...
- 求next[j] 就是从 k = next[j - 1]开始检查 s[k + 1] = s[j] 是否成立，不成立就一直往前找 next （最长 border）
例题
- 问题1：求字符串 A 的最短周期
- 做法：根据 pre(A, k) 是 A 的 border 等价于 |A| - k 是 A 的周期，我们有 A 的最短周期 = |A| - A 的最长 border = N - next[N]
- 问题2：给出字符串 A 和 B，求在 A 中最多能选出多少个互不重叠的 B 串
- 做法：KMP找出所有next[j] = |B|的位置，从左到右贪心，能选则选