记录自 10.15 讲课。我们不生产讲义，我们只是讲义的搬运工。

文本串 $S$，找模式串 $T$（串的模式匹配问题）

$S=$ ababab，$T=$ abab → 匹配位置：$1$，$3$

定义 $n=|S|$，$m=|T|$

• Brute Force（朴素算法）

$S_{i\dots i+m-1}=T$ → $i$ 位置为一个答案

i,j ← 0
ans ← emptyset
s[n+1]←'#' t[n+1]←'*'
while i<n
. if s[i+1]=t[j+1]
. . i←i+1, j←j+1
. . if j=m
  . . . ans ← ans U {i-m+1}
. else
. . i←i-j+1, j←0

最好：$O(m)$ 平均：$O(n-m)$ 最坏：$O((n-m)m)$

→ 要求降低最坏情况复杂度

KMP 算法设计思想

假设朴素算法进行过程中，遇到 $S_{i+1}\neq T_{j+1}$（$j>0$）

观察，若 $T_{1\dots j}$ 长为 $L=j-1$ 的前、后缀不等，则 $S_{i-l+1\dots i-l+m}\neq T$，故此时可跳过 $i\larr i-l$，直接令 $i\larr i-l+1$（原本朴素算法这样做）

更一般地：若 $T_{1\dots j}$ 的长 $l(0<l<j)$ 的前、后缀不相等，则 $S_{i-l+1\dots i-l+m}\neq T$。

找到 $[0,j)$ 中最大整数 $k$ 使得 $T_{1\dots j}$ 的长为 $k$ 的前、后缀相等。

对于所有 $k+1\leq l \leq j-1$，$S_{i-l+1\dots i-l+m}\neq T$。

接下来应该去做的是：对 $x=i-k$，检查 $S_{x+1\dots x+m}=T$?

法一：令 $i\larr i-k,j\larr 0$，然后逐位比较。

法二（更聪明的做法）：令 $i$ 不变，$j\larr k$。$k$ 见上述定义。

$\pi$ （最长 border 长度）的定义及 KMP 主过程描述

注意：$\pi$ 的定义与 nxt 数组稍微有差异。（这是老师说的）

对 $0<j\leq m$，令 $\pi_j$ 表示 $[0,j)$ 中最大整数 使得 $T_{1\dots j}$ 的长为 $\pi_j$ 的前、后缀相等。

假设 $\pi$ 已算好，匹配可改为以下算法：

i,j ← 0
ans ← emptyset
while i<n
. if s[i+1]=t[j+1]
. . i←i+1 j←j+1
. . if j=m
. . . ans ← ans U {i-m+1}
. . . j ← pi[j]
. else if j=0
. . i ← i+1
. else
. . j ← pi[j]

• 复杂度分析

1. $i$ 不会回溯，$i\larr i+1$、$j\larr j+1$ 执行 $\leq n$ 次。
2. $i\larr i+1$ 执行 $\leq n$ 次意味 $j\larr\pi_j$ 最多执行 $n$ 次。

→ 因此复杂度 $O(n)$ （$m\leq n$ 时）【难点：$j$ 不是单增的】

因 $i$ 不回溯，可以“流水作业”式从输入一边读入一边查找。

• 小结

$[0,j)$ 中最大整数 $\pi_j$ 使得 $T_{1\dots j}$ 的长为 $\pi_j$ 的前、后缀相等。

$\pi_{1\dots m}$ 叫做 failure function（失配转移函数），partial match table（部分匹配表）

$\pi$ 只和 $T$ 有关。

→ 如何计算 $\pi$？

$\pi$ 的计算

$\pi_{i+1}=j+1 \larr \rarr$

$j$ 是满足如下性质的最大整数：$T_{1\dots j+1}$ 是 $T_{1\dots i+1}$ 的真后缀（不与原串相等的后缀）。（注意 $j$ 可能为 $-1$，即 $j$ 不存在）

$\pi_{i+1}$ 的计算方法：

找到满足如下性质的最大整数 $j$：

(1) $T_{1\dots j}$ 是 $T_{1\dots i}$ 的真后缀

(2) $T_{j+1}=T_{i+1}$

当存在 $j\geq 0$，$\pi_{i+1}=j+1$

若 $j$ 不存在则 $\pi_{i+1}=0$

→ 问题转化为，给定 $i>1$，找出最大 $j$ 使得

(1) $T_{1\dots j}$ 是 $T_{1\dots i}$ 的真后缀

(2) $T_{j+1}=T_{i+1}$

思想：从小到大依次找出满足（1）的各个 $j$，直到 $j$ 满足（2）就确定答案并推出求 $\pi_{i+1}$ 的子过程。

j ← pi[i]
while true
. if t[j+1]=t[i+1]
. . pi[i+1] ← j+1
. . break
. else if j=0
. . pi[j+1] ← 0
. . break
. else
. . 找到比j更小的最大的j'使得T[1,j']是T[1,i]真后缀。
. . j ← j'

定理：$\{j|T_{1\dots j}是T_{1\dots i}的真后缀\}=$

$\{\pi_i,\pi_{\pi_i}\dots 0\}$ 对所有 $i>0$ 成立。

证明：$\pi_i=0$ 显然成立。

假设 $\pi_i>0$

注意：$\{j<i'|T_{1\dots j}是T_{1\dots \color{#e00}i}的真后缀\}$

$=\{j<i'|T_{1\dots j}是T_{1\dots \color{#e00}i'}的真后缀\}$

$=\{\pi_{i'},\pi_{\pi_{i'}}\dots 0\}$（根据归纳法）

因此 $\{j|T_{1\dots j}是T_{1\dots i}的真后缀\}=$

$=\{\pi_{i'},\pi_{\pi_{i'}}\dots 0\}∪\{i'\}=\{\pi_{i},\pi_{\pi_i}\dots 0\}$

于是将 $j'=\pi_j$ 填入倒数第二行，求 $\pi_{i+1}$ 的过程转化为

j ← pi[i]
while true
. if t[j+1]=t[i+1]
. . pi[i+1] ← j+1
. . break
. else if j=0
. . pi[j+1] ← 0
. . break
. else
. . j ← pi[j]

求所有 $\pi$ 的过程即为：

i←1 j←0
pi[1] ← 0
while i<m
. if t[i+1]=t[j+1]
. . i←i+1 j←j+1
. . pi[i] ← j
. else if j=0
. . i ← i+1
. . pi[i] ← j
. else
. . j ← pi[j]

• 小结

先利用模式串 $T$ 自己与自己比较得到 $\pi$，再利用 $\pi$ 高效匹配 $S$。最坏复杂度 $O(n+m)$

启示：Reflect yourself before judging others.

了解 KMP 主过程的重要性质

主过程与预处理 $\pi$ 的过程非常相似，why?

因为某种原因，该段已被删减。

KMP 的扩展应用

$\pi$ 树 / 失配树

所有 $\pi_i$ 向 $i$ 连边形成的以 $0$ 为根的树。

$S$ 的两个前缀的最长公共 border 可转化为对应 $\pi$ 树上两点的 LCA。

Z 算法（扩展 KMP）

【注意，这一段中下标从 $0$ 开始，有些奇怪。】

$i>0$ 时，Z 函数 $z_i$ 的定义为：最大整数 $z_i$ 使得 $T_{0\dots n-1}$、$T_{i\dots n-1}$ 的长为 $z_i$ 的二前缀相等。(也就是 $T_{0\dots n-1}$ 和 $T_{i\dots n-1}$ 的最长公共前缀长度)

在该算法中，从 $1$ 到 $n-1$ 顺次计算 $z_i$。计算 $z_i$ 的过程中，利用已算好的 $z_{0\dots i-1}$ 加速。（当然实际上应该$z_0=n$，但因为计算中 $S_{0\dots n-1}=S_{0\dots n-1}$ 的条件啥用没有，所以不妨让 $z_0=0$）。

对于 $i$，称区间 $[i,i+z_i-1]$ 是 $i$ 的匹配段（Z-Box）。

计算 $z_i$ 时，维护右端点最靠右的已知匹配段（记作 $[l,r]$，已知即需满足 $l \leq i$）。根据定义，$S_{l\dots r}$ 是 $S$ 的前缀。初始时设 $l=r=0$（一切还在未知中）。在计算 $z_i$ 过程中：

• 若 $i\leq r$，则根据 $[l,r]$ 定义有 $S_{i\dots r}=S_{i-l\dots r-l}$，因此 $z_i\geq\min(z_{i-l},r-i+1)$ （和 $r-i+1$ 取 min 是因为 $r$ 右边的部分还不知道是什么，只能靠暴力来探索了。）即：
• • 若 $z_{i-l}<r-i+1$ 则 $z_i=z_{i-l}$。
• • 若 $z_{i-l}\geq r-i+1$ 则让 $z_i\leq z_{i-l}$ 然后暴力尝试扩展直到不能再扩展为止。
• 若 $i>r$，那么 $i$ 的位置是没被探索过的，直接暴力尝试扩展。

每次求出 $z_i$ 后，若 $i+z_i-1>r$（$i$ 开头匹配段的右段到达了前人未曾涉足的地方），则让 $l\larr i,r\larr i+z_i-1$。

时间复杂度：$O(n)$

例题

CF126B Password（KMP $\pi$ 数组或 Z 函数）

P5829 【模板】失配树 这题已经 SPFA 了，大致题意如下：给定一长为 $n\leq 10^6$ 的字符串 $S$，$m\leq 5\times 10^5$ 次询问，每次询问它的两个前缀的最长公共 border。

P5910

HDU2087

POJ1406