一文吃透字符串匹配！

主要参考算法导论，修正原文错误、易混淆翻译，整合相关习题实战

字符串匹配

在编辑文本程序过程中, 我们经常需要在文本中找到某个模式的所有出现位置。典型情况 是, 一段正在被编辑的文本构成一个文件, 而所要搜寻的模式是用户正在输入的特定的关键字。 有效地解决这个问题的算法叫做字符串匹配算法, 该算法能够极大提高编辑文本程序时的响应 效率。在其他很多应用中, 字符串匹配算法用于在 DNA 序列中搜寻特定的序列。在网络搜索引 擎中也需要用这种方法来找到所要查询的网页地址。

字符串匹配问题的形式化定义如下: 假设文本是一个长度为 $n$ 的数组 $T[1, n]$, 而模式是一 个长度为 $m$ 的数组 $P[1 . . m]$, 其中 $m \leqslant n$, 进一步假设 $P$ 和 $T$ 的元素都是来自一个有限字母集 $\Sigma$ 的字符。例如, $\Sigma=\{0,1\}$ 或者 $\Sigma=\{a, b, \cdots, z\}$ 。字符数组 $P$ 和 $T$ 通常称为字符串。

如图 32-1 所示, 如果 $0 \leqslant s \leqslant n-m$, 并且 $T[s+1 \ldots s+m]=P[1 \ldots m]$ (即如果 $T[s+j]=$ $P[j]$, 其中 $1 \leqslant j \leqslant m$ ), 那么称模式 $P$ 在文本 $T$ 中出现, 且偏移为 $s$ (或者等价地, 模式 $P$ 在文本 $T$ 中出现的位置是以 $s+1$ 开始的)。如果 $P$ 在 $T$ 中以偏移 $s$ 出现, 那么称 $s$ 是有效偏移; 否则, 称它为无效偏移。字符串匹配问题就是找到所有的有效偏移, 使得在该有效偏移下, 所给的模式 $P$ 出现在给定的文本 $T$ 中。

图 32-1

字符串匹配问题的一个例子, 在该例子中, 我们试图找到模式 $P=\mathrm{abaa}$ 在文本 $T=a b c a b a a b c a b a c$ 中所有出现的位置。模式只在这个文本中出现一次, 在偏移 $s=3$ 处, 因此我们称 $s$ 为有效偏移。用坚线连接了每一个模式中的字符和与其对应的文本中的字符，所有匹配的字符都被涂上了阴影

除了在 $32.1$ 节将要复习的朴素算法外, 本章中的每个字符串匹配算法都基于模式进行了预 处理, 然后找到所有有效偏移; 我们称第二步为“匹配”。图 32-2 给出了本章中每个算法的预处理时间和匹配时间。每个算法的总运行时间是预处理时间和匹配时间的和。32.2 节描述了一种 由 Robin 和 Karp 发现的一种有趣的字符串匹配算法。尽管这种算法在最坏情况下的运行时间 $\Theta((n-m+1) m)$ 并不比朴素算法好, 但就平均情况和实际情况来说, 该算法效果要好得多。这种算法也可以很好地推广, 用以解决其他的模式匹配问题。32.3 节描述一种字符串匹配算法, 该算法通过构造一个有限自动机, 专门用来搜寻所给的模式 $P$ 在文本中出现的位置。这种算法需要 $O(m|\Sigma|)$ 的预处理时间, 但是仅仅需要 $\Theta(n)$ 的匹配时间。 $32.4$ 节介绍与其类似但是更加巧妙的 Knuth-Morris-Pratt(或 KMP)算法; 该算法的匹配时间同样为 $\Theta(n)$, 但是它缩短了预处理时间，仅需$\Theta(m)$ 。

符号和术语

在本章中, 我们只考虑有限长度的字符串。我们用 $\Sigma^{\ast}$ 来表示包含所有有限长度的字符串的集合, 该字符串是由字母表 $\Sigma$ 中的字符组成。长度为零的空字符串用 $\varepsilon$ 表示, 也属于 $\Sigma^{\ast}$ 。一个字符串 $x$ 的长度用 $|x|$ 来表示。两个字符串 $x$ 和 $y$ 的连结 (concatenation)用 $x y$ 表示, 长度为 $|x|+|y|$, 由 $x$ 的字符后接 $y$ 的字符构成。

如果对某个字符串 $y \in \Sigma^{\ast}$ 有 $x=w y$, 则称字符串 $w$ 是字符串 $x$ 的前缀, 记作 $w \sqsubset x$ 。注意 到如果 $w \sqsubset x$ , 则 $|w| \leqslant|x|$ 。类似地, 如果对某个字符串 $y$ 有 $x=y w$, 则称字符串 $w$ 是字符串 $x$ 的后缀, 记作 $w \sqsupset x$ 。和前缀类似, 如果 $w \sqsupset x$, 则 $|w| \leqslant|x|$ 。例如, 我们有 $\mathrm{ab} \sqsubset \mathrm{abcca}$ 和 $cca \sqsupset a b c c a$ 。空字符串 $\varepsilon$ 同时是任何一个字符串的前缀和后缀。对于任意字符串 $x$ 和 $y$ 以及任意字符 $a$, 当且仅当 $x a \sqsupset y a$ 时, 我们有 $x \sqsupset y$ 。请注意, $\sqsubset$和 $\sqsupset$ 都是传递关系。下面的引理在稍后将会用到。

引理 32. 1(后缀重叠引理) 假设 $x, y$ 和 $z$ 是满足 $x \sqsupset z$ 和 $y \sqsupset z$ 的字符串。如果 $|x| \leqslant|y|$, 那么 $x \sqsupset y$ ; 如果 $|x| \geqslant|y|$, 那么 $y \sqsupset x$ ; 如果 $|x|=|y|$, 那么 $x=y$ 。

为了使符号简洁, 我们把模式 $P[1 . . m]$ 的由 $k$ 个字符组成的前缀 $P[1 \ldots k]$ 记作 $P_{k}$ 。因此 $P_{0}=\varepsilon, P_{m}=P=P[1 . . m]$ 。与此类似, 我们把文本 $T$ 中由 $k$ 个字符组成的前缀记为 $T_{k}$ 。采用这种记号, 我们能够把字符串匹配问题表述为: 找到所有偏移 $s(0 \leqslant s \leqslant n-m)$, 使得 $P \sqsupset T_{s+m}$ 。

在我们的伪代码中, 把比较两个等长字符串是否相等的操作当做操作原语。如果字符串比较是从左到右进行的, 并且当遇到一个字符不匹配时, 比较操作终止, 则可以假设在这样的一个检测中所花费的时间是关于已匹配成功字符数目的线性函数。更准确地说, 假设检测“ $x==y$ ” 需要时间 $\Theta(t+1)$, 其中 $t$ 是满足 $z \sqsubset x$ 和 $z \sqsubset y$ 的最长字符串 $z$ 的长度。(我们用 $\Theta(t+1)$ 而不是 $\Theta(t)$, 是为了更好地处理 $t=0$ 的情况; 尽管第一个字符比较时就不匹配, 但是在运行这个比较 操作时仍然花费了一定的时间。)

朴素字符串匹配算法

朴素字符串匹配算法是通过一个循坏找到所有有效偏移, 该循环对 $n-m+1$ 个可能的 $s$ 值进行检测, 看是否满足条件 $P[1 . . m]=T[s+1 . . s+m]$ 。

$$\begin{aligned} &\text { NAIVE-STRING-MATCHER }(T, P) \\ &1 \quad n=T . \text { length } \\ &2 \quad m=P . \text { length } \\ &3 \quad \text { for } s=0 \text { to } n-m \\ &4 \quad \quad \text { if } P[1 . . m]==T[s+1 . . s+m] \\ &5\quad \quad \quad\text { print "Pattern occurs with shift" } s \end{aligned}$$

图 32-4 描绘的朴素字符串匹配过程可以形象地看成一个包含模式的“模板”沿文本滑动, 同时对每个偏移都要检测模板上的字符是否与文本中对应的字符相等。第 $3 \sim 5$ 行的 for 循环考察每一个可能的偏移。第 4 行的测试代码确定当前的偏移是否有效; 该测试隐含着一个循环, 该循环用于逐个检测对应位置上的字符, 直到所有位置都能成功匹配或者有一个位置不能匹配为止。 第 5 行用于打印输出每一个有效偏移 $s$ 。

在最坏情况下, 朴素字符串匹配算法运行时间为 $O((n-m+1) m)$ 。例如, 在考察文本字符串 $a^{n}$ (一串由 $n$ 个 $a$ 组成的字符串) 和模式 $a^{m}$ 时, 对偏移 $s$ 的 $n-m+1$ 个可能值中的每一个, 在第 4 行中比较相应字符的隐式循环必须执行 $m$ 次来确定偏移的有效性。因此, 最坏情况下的运行时间是 $\Theta((n-m+1) m)$, 如果 $m=\lfloor n / 2\rfloor$, 则运行时间是 $\Theta\left(n^{2}\right)$ 。由于不需要预处理, 朴素字符串匹配算法运行时间即为其匹配时间。

我们将会看到, NAIVE-STRINGMATCHER 并不是解决字符串匹配问题的最好过程。事实上, 在本章中, 我们将会发现 Knuth-Morris-Pratt 算法在最坏情况下比朴素算法好得多。这种朴素字符串匹配算法效率不高, 是因为当其他无效的 $s$ 值存在时, 它也只关心一个有效的 $s$ 值, 而完全忽略了检测无效 $s$ 值时获得的文本的信息。然而这样的信息可能非常有用。例如, 如果 $P=a a b$ 并且我们发现 $s=0$ 是有效的, 由于 $T[4]=b$, 那么偏移 1、2 或 3 都不是有效的。在后续 章节中, 我们将考察能够充分利用这部分信息的几种方法。

Rabin-Karp 算法（字符串前缀哈希）

在实际应用中, Rabin 和 Karp 所提出的字符串匹配算法能够较好地运行, 并且还可以从中归纳出相关问题的其他算法, 比如二维模式匹配。 Rabin-Karp算法的预处理时间是 $\Theta(m)$, 并且在最坏情况下，它的运行时间为 $\Theta((n-m+1) m)$ 。基于一些假设，在平均情况下，它的运行时间还是比较好的。

该算法运用了初等数论概念, 比如两个数相对于第三个数模等价。如果想要了解相关的定义, 请参照 $31.1$ 节的内容。

为了便于说明, 假设 $\Sigma=\{0,1,2, \cdots, 9\}$, 这样每个字符都是十进制数字。(在通常情况下, 可以假定每个字符都是以 $d$ 为基数表示的数字, 其中 $d=|\Sigma|$ ) 。我们可以用长度为 $k$ 的十进制数来表示由 $k$ 个连续的字符组成的字符串。因此, 字符串 31415 对应着十进制数 31415 。假如输入的字符既可以看做是图形符号, 也可以看做是数字, 那么在本节中我们会发现, 运用我们的标准文本字体, 把它们表示为数字会更加方便。

给定一个模式 $P[1 . . m]$, 假设 $p$ 表示其相应的十进制值。类似地, 给定文本 $T[1 . . n]$, 假设 $t_{s}$ 表示长度为 $m$ 的子字符串 $T[s+1 \ldots s+m]$ 所对应的十进制值, 其中 $s=0,1, \cdots, n-m$ 。当然, 只有在 $T[s+1 . . s+m]=P[1 . . m]$ 时, $t_{s}=p$ 。如果能在时间 $\Theta(m)$ 内计算出 $p$ 值, 并在总时间 $\Theta(n-m+1)$ 内计算出所有的 $t_{s}$ 值 , 那么通过比较 $p$ 和每一个 $t_{s}$ 值, 就能在 $\Theta(m)+\Theta(n-$ $m+1)=\Theta(n)$ 时间内找到所有的有效偏移 $s$ 。（目前, 暂不考虑 $p$ 和 $t_{s}$ 值可能很大的问题。）

我们可以运用霍纳法则(参见 $30.1$ 节)在时间 $\Theta(m)$ 内计算出 $p$ ：

$$p=P[m]+10(P[m-1]+10(P[m-2]+\cdots+10(P[2]+10 P[1]) \cdots))$$

类似地, 也可以在 $\Theta(m)$ 时间内根据 $T[1 . . m]$ 计算出 $t_{0}$ 的值。

为了在时间 $\Theta(n-m)$ 内计算出剩余的值 $t_{1}, t_{2}, \cdots, t_{n-m}$, 我们需要在常数时间内根据 $t_{s}$ 计算出 $t_{s+1}$, 因为

$$t_{s+1}=10\left(t_{s}-10^{m-1} T[s+1]\right)+T[s+m+1]$$

减去 $10^{m-1} T[s+1]$ 就从 $t_{s}$ 中去掉了高位数字, 再把结果乘以 10 就使得数字向左移动一个数位, 然后加上 $T[s+m+1]$, 则加入一个适当的低位数字。例如, 如果 $m=5$ 并且 $t_{s}=31415$, 那么我们希望能够去掉高位数字 $T[s+1]=3$, 并且加入新的低位数字 $($ 假设是 $T[s+5+1]=2)$, 从而获得:

$$t_{s+1}=10(31415-1000.3)+2=14152 \quad \quad(32.1)$$

如果能够预先计算出常数 $10^{m-1}$ (用 $31.6$ 节中介绍的技术——反复平方法快速求幂, 就可以在 $O(\lg m)$ 的时间内完成这一计算过程, 但对于这个应用, 一种简便的运行时间为 $O(m)$ 的算法就足够完成任务), 则每次执行式 $(32.1)$ 的计算时, 需要执行的算术运算的次数为常数。因此, 可以在时间 $\Theta(m)$ 内计算出 $p$, 在时间 $\Theta(n-m+1)$ 内计算出所有 $t_{0}, t_{1}, t_{2}, \cdots, t_{n-m}$ 的值。因而可以用 $\Theta(m)$ 的预处理时间和 $\Theta$ $(n-m+1)$ 的匹配时间找到所有模式 $P[1 . . m]$ 在文本 $T[1 . . n]$ 中出现的位置。

到目前为止, 我们有意回避的一个问题是: $p$ 和 $t_{s}$ 的值可能太大, 导致不能方便地对其进行操作。如果 $P$ 包含 $m$ 个字符, 那么关于在 $p$（$m$ 数位长 $)$ 上的每次算术运算需要“常数”时间这一假设就不合理了。幸运的是, 我们可以很容易地解决这个问题, 如图 32-5 所示: 选取一个合适的模 $q$ 来计算 $p$ 和 $t_{s}$ 的模。我们可以在 $\Theta(m)$ 的时间内计算出模 $q$ 的 $p$ 值, 并且可以在 $\Theta(n-m+1)$ 时间内计算出模 $q$ 的所有 $t_{s}$ 值。如果选模 $q$ 为一个素数, 使得 $10 q$ 恰好满足一个计算机字长, 那么可以用单精度算术运算执行所有必需的运算。在一般情况下, 采用 $d$ 进制的字母表 $\{0,1, \cdots, d-1\}$ 时, 选取一个 $q$ 值, 使得 $d q$ 在一个计算机字长内, 然后调整递归式(32.1), 使其能够对模 $q$ 有效, 式子变为:

$$t_{s+1}=\left(d\left(t_{s}-T[s+1] h\right)+T[s+m+1]\right) \bmod q \quad \quad(32.2)$$

其中 $h \equiv d^{m-1}(\bmod q)$ 是一个具有 $m$ 数位的文本窗口的高位数位上的数字“1”的值。

但是基于模 $q$ 得到的结果并不完美: $t_{s} \equiv p(\bmod q)$ 并不能说明 $t_{s}=p$ 。但是另一方面, 如果 $t_{s} \neq p(\bmod q)$, 那么可以断定 $t_{s} \neq p$, 从而确定偏移 $s$ 是无效的。因此可以把测试 $t_{s} \equiv p(\bmod q)$ 是否成立作为一种快速的启发式测试方法用于检测无效偏移 $s$ 。任何满足 $t_{s} \equiv p(\bmod q)$ 的偏移 $s$ 都需要被进一步检测, 看 $s$ 是真的有效还是仅仅是一个伪命中点。这项额外的测试可以通过检测条件 $P[1 . . m]=T[s+1 \ldots s+m]$ 来完成, 如果 $q$ 足够大, 那么这个伪命中点可以尽量少出现, 从而使额外测试的代价降低。

下面的过程准确描述了上述思想。过程的输入是文本 $T$, 模式 $P$, 使用基数 $d$ (其典型取值为 $|\Sigma|$ ) 和素数 $q$ 。

$$\begin{aligned} &\text {RABIN-KARP-MATCHER }(T, P, d, q) \\ 1 & \quad n=T . \text { length } \\ 2 & \quad m=P . \text { length } \\ 3 & \quad h=d^{m-1} \bmod q \\ 4 & \quad p=0 \\ 5 & \quad t_{0}=0 \\ 6 & \quad \text {for } i=1 \text { to } \mathrm{m} \\ 7 & \quad \quad p=(d p+P[i]) \bmod q \\ 8 & \quad \quad t_{0}=\left(d t_{0}+T[i]\right) \bmod q \\ 9 & \quad \text {for } s=0 \text { to } n-m \\ 10 & \quad \quad \text {if } p==t_{s} \\ 11 & \quad \quad \quad \text {if } P[1 . . m]==T[s+1 . . s+m] \\ 12 & \quad \quad \quad \quad \text {print } \text { “Pattern occurs with shift” } s \\ 13 & \quad \quad \text {if } s<n-m \\ 14 & \quad \quad \quad t_{s+1}=\left(d\left(t_{s}-T[s+1] h\right)+T[s+m+1]\right) \bmod q \end{aligned}$$

RABIN-KARP-MATCHER 执行过程如下。所有的字符都假设是 $d$ 进制的数字。仅为了说明的清楚, 给 $t$ 添加了下标, 去除所有下标不会影响程序运行。第 3 行初始化 $m$ 位窗口中高位上的值 $h$ 。第 $4 \sim 8$ 行计算出 $P[1 . . m] \bmod q$ 的值 $p$, 计算出 $T[1 . . m] \bmod q$ 的值 $t_{0}$ 。第 $9 \sim 14$ 行的 for 循环迭代遍历了所有可能的偏移 $s$, 保持如下的不变量:

• 第 10 行无论何时执行, 都有 $t_{s}=T[s+1 \ldots s+m] \bmod q$ 。

如果在第 10 行中有 $p=t_{s}$ (一个“命中点”), 那么在第 11 行检测是否 $P[1 . . m]=T[s+1 \ldots s+m]$, 用以排除它是伪命中点的可能性。第 12 行打印出所有找到的有效偏移。如果 $s<n-m$ (在第 13 行中检测), 则至少再执行一次 for 循环, 这时首先执行第 14 行以保证再次执行到第 10 行时循环不变式依然成立。第 14 行直接利用等式 (32.2), 就可以在常数时间内由 $t_{s} \bmod q$ 的值计算出 $t_{s+1} \bmod q$ 的值。

RABIN-KARP-MATCHER 的预处理时间为 $\Theta(m)$, 在最坏情况下, 它的匹配时间是 $\Theta((n-m+1) m)$, 因为 Rabin-Karp 算法和朴素字符串匹配算法一样, 对每个有效偏移进行显式验证。如果 $P=a^{m}$ 并且 $T=a^{n}$, 由于在 $n-m+1$ 个可能的偏移中每一个都是有效的, 则验证所需的时间为 $\Theta((n-m+1) m)$ 。

在许多实际应用中, 我们希望有效偏移的个数少一些 (如只有常数 $c$ 个)。在这样的应用中, 加上处理伪命中点所需时间, 算法的期望匹配时间为 $O((n-m+1)+c m)=O(n+m)$ 。减少模 $q$ 的值就如同从 $\Sigma^{\ast}$ 到 $\mathbf{Z}_{q}$ 上的一个随机映射, 基于这个假设, 可以对算法进行启发式分析。（参见 $11.3 .1$ 节中对散列除法的讨论, 要正规证明这个假设是比较困难的, 但是有一种可行的方法, 就是假设 $q$ 是从适当大的整数中随机得出的, 我们在此将不继续纠缠形式化的问题。）然后我们能够预计伪命中的次数为 $O(n / q)$, 因为可以估计出任意的 $t_{s}$ 模 $q$ 的余数等价于 $p$ 的概率为 $1 / q$ 。因为第 10 行中的测试会在 $O(n)$ 个位置上失败, 且每次命中的时间代价是 $O(m)$, 因此, Rabin-Karp 算法的期望运行时间为:

$$O(n)+O(m(v+n / q))$$

其中 $v$ 是有效偏移量。如果 $v=O(1)$ 并且 $q \geqslant m$, 则这个算法的运行时间是 $O(n)$ 。也就是说, 如果期望的有效偏移量很少 $(O(1))$, 而选取的素数 $q$ 大于模式的长度, 则可以估计 Rabin-Karp 算 法的匹配时间为 $O(n+m)$, 由于 $m \leqslant n$, 这个算法的期望匹配时间是 $O(n)$ 。

利用有限自动机进行字符串匹配

很多字符串匹配算法都要建立一个有限自动机, 它是一个处理信息的简单机器, 通过对文本字符串 $T$ 进行扫描, 找出模式 $P$ 的所有出现位置。本节将介绍一种建立这样自动机的方法。这些字符串匹配的自动机都非常有效: 它们只对每个文本字符检查一次, 并且检查每个文本字符时所用的时间为常数。因此, 在模式预处理完成并建立好自动机后进行匹配所需要的时间为 $\Theta(n)$ 。但是, 如果 $\Sigma$ 很大, 建立自动机所需的时间也可能很多。 $32.4$ 节将描述解决这个问题的一种巧妙方法。

本节首先定义有限自动机。然后, 我们要考察一种特殊的字符串匹配自动机, 并展示如何利用它找出一个模式在文本中的出现位置。最后, 我们将说明对一个给定的输入模式, 如何构造相应的字符串匹配自动机。

有限自动机

如图 32-6 所示, 一个有限自动机 $M$ 是一个 5 元组 $\left(Q, q_{0}, A, \Sigma, \delta\right)$, 其中:

• $Q$ 是状态的有限集合。
• $q_{o} \in Q$ 是初始状态。
• $A \subseteq Q$ 是一个特殊的接受状态集合。
• $\sum$ 是有限输入字母表。
• $\delta$ 是一个从 $Q \times \sum$ 到 $Q$ 的函数, 称为 $M$ 的转移函数。

有限自动机开始于状态 $q_{0}$, 每次读入输入字符串的一个字符。如果有限自动机在状态 $q$ 时读入了字符 $a$, 则它从状态 $q$ 变为状态 $\delta(q, a)$ (进行了一次转移)。每当其当前状态 $q$ 属于 $A$ 时，就说自动机 $M$ 接受了迄今为止所读入的字符串。没有被接受的输入称为被拒绝的输入。

有限自动机 $M$ 引人一个函数 $\phi$, 称为终态函数, 它是从 $\Sigma^{\ast}$ 到 $Q$ 的函数, 满足 $\phi(w)$ 是 $M$ 在扫描字符串 $w$ 后终止时的状态。因此, 当且仅当 $\phi(w) \in A$ 时, $M$ 接受字符串 $w$ 。我们可以用转移函数递归定义 $\phi$ :

$$\begin{aligned} &\phi(\varepsilon)=q_{0}, \\ &\phi(w a)=\delta(\phi(w), a), \quad w \in \Sigma^{*}, a \in \Sigma \end{aligned}$$

字符串匹配自动机

对于一个给定的模式 $P$, 我们可以在预处理阶段构造出一个字符串匹配自动机, 根据模式构造出相应的自动机后, 再利用它来搜寻文本字符串。图 32-7 说明了用于匹配模式 $P=\mathrm{ababaca}$ 的 有限自动机的构造过程。从现在开始, 假定 $P$ 是一个已知的固定模式。为了使说明简洁, 在下面的符号中将不指出对 $P$ 的依赖关系。

为了详细说明与给定模式 $P[1 . . \mathrm{m}]$ 对应的字符串匹配自动机, 首先定义一个辅助函数 $\sigma$, 称为对应 $P$ 的后缀函数。函数 $\sigma$ 是一个从 $\Sigma^{\ast}$ 到 $\{0,1, \cdots, m\}$ 上的映射, $\sigma(x)$ 是 $P$ 的前缀和 $x$ 后缀的最长匹配长度

$$\sigma(x)=\max \left\{k: P_{k} \sqsupset x\right\} \quad \quad (32.3)$$

因为空字符串 $P_{0}=\varepsilon$ 是每一个字符串的后缀, 所以后缀函数 $\sigma$ 是良定义的。例如, 对模式 $P=$ $\mathrm{ab}$, 有 $\sigma(\varepsilon)=0, \sigma(ccaca )=1, \sigma( ccab )=2$ 。对于一个长度为 $m$ 的模式 $P, \sigma(x)=m$ 当且仅当 $P \sqsupset x$ 。根据后缀函数的定义：如果 $x \sqsupset y$， 则 $\sigma (x) \leqslant \sigma(y)$ 。

给定模式 $P[1..m]$ ，其相应的字符串匹配自动机定义如下：

• 状态集合 $Q$ 为 $\{0,1, \cdots, m\}$ 。开始状态 $q_{0}$ 是 0 状态, 并且只有状态 $m$ 是唯一被接受的状态

• 对任意的状态 $q$ 和字符 $a$， 转移函数 $\delta$ 定义如下:

  $$\delta(q, a)=\sigma\left(P_{q} a\right)$$

我们定义 $\delta(q, a)=\sigma\left(P_{q} a\right)$, 目的是记录已得到的与模式 $P$ 匹配的文本字符串 $T$ 的最长前缀。考虑最近一次扫描 $T$ 的字符。为了使 $T$ 的一个子串 (以 $T[i]$ 结尾的子串) 能够和 $P$ 的某些前缀 $P_{j}$ 匹配, 前缀 $P_{j}$ 必须是 $T_{i}$ 的一个后缀。假设 $q=\phi\left(T_{i}\right)$, 那么在读完 $T_{i}$ 之后, 自动机处在状态 $q$ 。设计转移函数 $\delta$, 使用状态数 $q$ 表示 $P$ 的前缀和 $T_{i}$ 后缀的最长匹配长度。也就是说, 在处于状态 $q$ 时, $P_{q} \sqsupset T_{i}$ 并且 $q=\sigma\left(T_{i}\right)$ 。（每当 $q=m$ 时, 所有 $P$ 的 $m$ 个字符都和 $T_{i}$ 的一个后缀匹配, 从而得到一个匹配。）因此, 由于 $\phi\left(T_{i}\right)$ 和 $\sigma\left(T_{i}\right)$ 都和 $q$ 相等, 我们将会看到 (在后续的定理 $32.4$ 中) 自动机保持下列等式成立:

$$\phi\left(T_{i}\right)=\sigma\left(T_{i}\right)$$

如果自动机处在状态 $q$ 并且读入下一个字符 $T[i+1]=a$, 那么我们希望这个转换能够指向 $T_{i} a$ 的后缀状态, 它对应着 $P$ 的最长前缀, 并且这个状态是 $\sigma\left(T_{i} a\right)$ 。由于 $P_{q}$ 是 $P$ 的最长前缀, 也是 $T_{i}$ 的一个后缀, 那么这个 $P$ 的最长前缀同时也是 $T_{i} a$ 的一个后缀, 就不仅表示为 $\sigma\left(T_{i} a\right)$, 也可表示为 $\sigma\left(P_{q} a\right)$ 。(引理 $32.3$ 证明了 $\left.\sigma\left(T_{i} a\right)=\sigma\left(P_{q} a\right)\right)$ 因此, 当自动机处在状态 $q$ 时, 我们希望这个在字符 $a$ 上的转移函数能使自动机转移到状态 $\sigma\left(P_{q} a\right)$ 。

考虑以下两种情况。第一种情况是, $a=P[q+1]$, 使得字符 $a$ 继续匹配模式。在这种情况 下, 由于 $\delta(q, a)=q+1$, 转换沿着自动机的“主线”(图 32-7 中的粗边) 继续进行。第二种情况, $a \neq P[q+1]$, 使得字符 $a$ 不能继续匹配模式。这时我们必须找到一个更小的子串, 它是 $P$ 的前缀同时也是 $T_{i}$ 的后缀。因为当创建字符串匹配自动机时, 预处理匹配模式和自己, 转移函数很快就得出最长的这样的较小 $P$ 前缀。

让我们看一个例子。图 32-7 的字符串匹配自动机有 $\delta(5, c)=6$, 说明其是第一种情况, 匹配继续进行。为了说明第二种情况, 观察图 32-7 中的自动机, 有 $\delta(5, b)=4$ 。我们选择这个转换的原因是如果自动机在 $q=5$ 状态时读到一个 $\mathrm{b}$, 那么 $P_{q} \mathrm{~b}=\mathrm{ababab}$, 并且 $P$ 的最长前缀也是 ababab 的后缀 $P_{4}=\mathrm{abab}$ 。

为了清楚说明字符串匹配自动机的操作过程, 我们给出一个简单而有效的程序, 用来模拟这样一个自动机（用它的转移函数 $\delta$ 来表示）, 在输入文本 $T[1 . . n]$ 中, 寻找长度为 $m$ 的模式 $P$ 的出现位置。如同对于 $m$ 长模式的任意字符串匹配自动机, 状态集 $Q$ 为 $\{0,1, \cdots, m\}$, 初始状态为 0 , 唯一的接受状态是 $m$ 。

$$\begin{aligned} &\text { FINITE-AUTOMATON-MATCHER(T,} \delta \text{,m) } \\ 1 & \quad n=T \text { length } \\ 2 & \quad q=0 \\ 3 & \quad \text {for } i=1 \text { to } n \\ 4 & \quad \quad q=\delta(q, T[i]) \\ 5 & \quad \quad \text {if } q==m \\ 6 & \quad \quad \quad \text {print “Pattern occurs with shift” } i-m \end{aligned}$$

从 FINITE-AUTOMATON-MATCHER 的简单循环结构可以看出, 对于一个长度为 $n$ 的文本字符串, 它的匹配时间为 $\Theta(n)$ 。但是, 这一匹配时间没有包括计算转移函数 $\delta$ 所需要的预处理时间。我们将在证明 FINITE-AUTOMATON-MATCHER 的正确性以后, 再来讨论这一问题。

考察自动机在输入文本 $T[1 . . n]$ 上进行的操作。下面将证明自动机扫过字符 $T[i]$ 后, 其状态为 $\sigma\left(T_{i}\right)$ 。因为当且仅当 $P \sqsupset T_{i}, \sigma\left(T_{i}\right)=m$ 。所以当且仅当模式 $P$ 被扫描过之后自动机处于接受状态 $m$ 。为了证明这个结论, 要用到下面两条关于后缀函数 $\sigma$ 的引理。

引理 32. 2(后缀函数不等式) 对任意字符串 $x$ 和字符 $a, \sigma(x a) \leqslant \sigma(x)+1$ 。

证明 参照图 32-8, 设 $r=\sigma(x a)$ 。如果 $r=0$, 则根据 $\sigma(x)$ 非负, $\sigma(x a)=r \leqslant \sigma(x)+1$ 显然成 立。于是现在假定 $r>0$, 根据 $\sigma$ 的定义。有 $P_{r} \sqsupset x a$ 。所以, 把 $a$ 从 $P_{r}$ 与 $x a$ 的末尾去掉后, 得到 $P_{r-1} \sqsupset x_{\circ}$ 因此, $r-1 \leqslant \sigma(x)$, 因为 $\sigma(x)$ 是满足 $P_{k} \sqsupset x$ 的最大的 $k$ 值, 所以 $\sigma(x a)=r \leqslant \sigma(x)+1$ 。

引理 32. 3(后缀函数递归引理) 对任意 $x$ 和字符 $a$, 若 $q=\sigma(x)$, 则 $\sigma(x a)=\sigma\left(P_{q} a\right)$ 。

证明 根据 $\sigma$ 的定义, 有 $P_{q} \sqsupset x$ 。如图 32-9 所示, 有 $P_{q} a \sqsupset x a$ 。若设 $r=\sigma(x a)$, 则 $P_{r} \sqsupset$ $x a$, 并由引理 $32.2$ 知, $r \leqslant q+1$ 。因此可得 $\left|P_{r}\right|=r \leqslant q+1=\left|P_{q} a\right|$ 。因为 $P_{q} a$. $x a$ 和 $P_{r} \sqsupset x a$ 并且 $\left|P_{r}\right| \leqslant\left|P_{q} a\right|$, 所以由引理 $32.1$ 可知 $P_{r} \sqsupset P_{q} a$ 。因此可得 $r \leqslant \sigma\left(P_{q} a\right)$, 即 $\sigma(x a) \leqslant \sigma\left(P_{q} a\right)$, 但由于 $P_{q} a$ コ $x a$, 所以有 $\sigma\left(P_{q} a\right) \leqslant \sigma(x a)$, 从而证明 $\sigma\left(P_{q} a\right)=\sigma(x a)$ 。

现在我们就可以来证明用于描述字符串匹配自动机在给定输入文本上操作过程的主要定理 了。如上所述, 这个定理说明了自动机在每一步中仅仅记录所读入字符串后缀的最长前缀。换句话说, 自动机保持着不变式 (32.5)。

定理 32. 4 如果 $\phi$ 是字符串匹配自动机关于给定模式 $P$ 的终态函数, $T[1 . . n]$ 是自动机的输入文本, 则对 $i=0,1, \cdots, n, \phi\left(T_{i}\right)=\sigma\left(T_{i}\right)$ 。

证明 对 $i$ 进行归纳。对 $i=0$, 因为 $T_{0}=\varepsilon$, 定理显然成立。因此 $\phi\left(T_{0}\right)=0=\sigma\left(T_{0}\right)$ 。

现在假设 $\phi\left(T_{i}\right)=\sigma\left(T_{i}\right)$, 并证明 $\phi\left(T_{i+1}\right)=\sigma\left(T_{i+1}\right)$ 。设 $q$ 表示 $\phi\left(T_{i}\right), a$ 表示 $T[i+1]$, 那么,

$$\begin{aligned} \phi\left(T_{i+1}\right) &=\phi\left(T_{i} a\right) &\left(\text { 根据 } T_{i+1} \text { 和 } a \text { 的定义 }\right) \\ &=\delta\left(\phi\left(T_{i}\right), a\right) &(\text { 根据 } \phi \text { 的定义 }) \\ &=\delta(q, a) &(\text { 根据 } q \text { 的定义 }) \\ &=\sigma\left(P_{q} a\right) &(\text { 根据式 }(32.4) \text { 关于 } \delta \text { 的定义 }) \\ &=\sigma\left(T_{i} a\right) &(\text { 根据引理 } 32.3 \text { 和归纳假设 }) \\ &=\sigma\left(T_{i+1}\right) &\left(\text { 根据 } T_{i+1} \text { 的定义 }\right) \end{aligned}$$

根据定理 $32.4$, 如果自动机在第 4 行进入状态 $q$, 则 $q$ 是满足 $P_{q} \sqsupset T_{i}$ 的最大值。因此, 在 第 5 行有 $q=m$, 当且仅当自动机刚刚扫描了模式 $P$ 在文本中的一次出现位置。于是可以得出结论, FINITE-AUTOMATON-MATCHER 可以正确地运行。

计算转移函数

下面的过程根据一个给定模式 $P[1 . . m]$ 来计算转移函数 $\delta_{\circ}$

$$\begin{aligned} &\operatorname{COMPUTE}-\operatorname{TRANSITION-FUNCTION}(P, \Sigma) \\ &1 \quad m=P . \text { length } \\ &2 \quad \text {for } q=0 \text { to } m \\ &3 \quad \quad \text {for each charater } a \in \Sigma\\ &4 \quad \quad \quad k=\min (m+1, q+2)\\ &5 \quad \quad \quad \text {repeat }\\ &6 \quad \quad \quad \quad k=k-1\\ &6 \quad \quad \quad \text {until } P_{k} \sqsupset P_{q} a\\ &7 \quad \quad \quad \delta(q, a)=k\\ &8 \quad \text{return }\delta\\ \end{aligned}$$

这个过程根据在式 (32. 4) 中的定义直接计算 $\delta(q, a)$, 在从第 2 行和第 3 行开始的嵌套循环中, 要考察所有的状态 $q$ 和字符 $a$ 。第 $4 \sim 8$ 行把 $\delta(q, a)$ 置为满足 $P_{k} \sqsupset P_{q} a$ 的最大的 $k$ 。代码从 $k$ 的最大可能值 $\min (m, q+1)$ 开始。随着过程的执行, $k$ 逐渐递减, 直至 $P_{k} \sqsupset P_{q} a$, 这种情况必然会发生, 因为 $P_{0}=\varepsilon$ 是每个字符串的一个后缀。

COMPUTE-TRANSITION-FUNCTION 的运行时间为 $O\left(m^{3}|\Sigma|\right)$, 因为外循环提供了一个因子 $m\left|\sum\right|$ ，内层的 repeat 循环至多执行 $m+l$ 次, 而第 7 行的测试 $P_{k} \sqsupset P_{q} a$ 需要比较 $m$ 个字符。还存在速度更快的程序。如果能够利用精心计算出的模式 $P$ 的有关信息 (见练习 32. 4-8), 则根据 $P$ 计算出 $\delta$ 所需要的时间可以改进为 $O(m|\Sigma|)$ 。如果用改进后的过程来计算 $\delta$, 则对字母表 $\Sigma$, 我们能够找出长度为 $m$ 的模式在长度为 $n$ 的文本中的所有出现位置, 这需要 $O(m|\Sigma|)$ 的预处理时间和 $\Theta(n)$ 的匹配时间。

Knuth-Morris-Pratt 算法

现在来介绍一种由 Knuth、Morris 和 Pratt 三人设计的线性时间字符串匹配算法。这个算法无需计算转移函数 $\delta$, 匹配时间为 $\Theta(n)$, 只用到辅助函数 $\pi$, 它在 $\Theta(m)$ 时间内根据模式预先计算出来, 并且存储在数组 $\pi[1 . . m]$ 中。数组 $\pi$ 使得我们可以按需要“即时”有效地计算(在摊还意义上来说)转移函数 $\delta_{\circ}$ 粗略地说, 对任意状态 $q=0,1, \cdots, m$ 和任意字符 $a \in \Sigma, \pi[q]$ 的值包含了与 $a$ 无关但在计算 $\delta(q, a)$ 时需要的信息。由于数组 $\pi$ 只有 $m$ 个元素, 而 $\delta$ 有 $\Theta\left(m\left|\sum\right|\right)$ 个值, 所以通过预先计算 $\pi$ 而不是 $\delta$, 可以使计算时间减少一个 $\Sigma$ 因子。

关于模式的前缀函数

模式的前缀函数 $\pi$ 包含模式与其自身的偏移进行匹配的信息。这些信息可用于在朴素的字符串匹配算法中避免对无用偏移进行检测, 也可以避免在字符串匹配自动机中, 对整个转移函数 $\delta$ 的预先计算。

考察一下朴素字符串匹配算法的操作过程。图 32-10(a)展示了一个针对文本 $T$ 模板的一个特定偏移 $s$, 该模板包含模式 $P=\mathrm{ababaca}$ 。在这个例子中, $q=5$ 个字符已经匹配成功, 但模式的第 6 个字符不能与相应的文本字符匹配。 $q$ 个字符已经匹配成功的信息确定了相应的文本字符。已知的这 $q$ 个文本字符使我们能够立即确定某些偏移是无效的。在该图的实例中, 偏移 $s+1$ 必然是无效的, 因为模式的第一个字符(a)将与文本字符匹配, 该文本字符已知不能和模式的第一个字符匹配, 但是却能与模式的第二个字符(b)匹配。在图 32-10(b) 所示的偏移 $s^{\prime}=s+2$ 使模式前面三个字符和相应三个文本字符对齐后必定会匹配。在一般情况下，知道下列问题的答案将是很有用的:

假设模式字符 $P[1 . . q]$ 与文本字符 $T[s+1 .. s+q]$ 匹配, $s^{\prime}$ 是最小的偏移量, $s^{\prime}>s$, 那么对某些 $k<q$, 满足

$$P[1 \ldots k]=T\left[s^{\prime}+1 \ldots s^{\prime}+k\right] \quad \quad (32.6)$$

的最小偏移 $s^{\prime}>s$ 是多少, 其中 $s^{\prime}+k=s+q$ ？

换句话说, 已知 $P_{q} \sqsupset T_{s+q}$, 我们希望 $P_{q}$ 的最长真前缀 $P_{k}$ 也是 $T_{s+q}$ 的后缀。（由于 $s^{\prime}+k=$ $s+q$, 如果给出 $s$ 和 $q$, 那么找到最小偏移 $s^{\prime}$ 等价于找到最长前缀的长度 $k_{\circ}$ ) 我们把在 $P$ 前缀长度范围内的差值 $q-k$ 加人到偏移 $s$ 中, 用于找到新的偏移 $s^{\prime}$, 使得 $s^{\prime}=s+(q-k)$ 。在最好情况下, $k=0$, 因此 $s^{\prime}=s+q$, 并且立刻能排除偏移 $s+1, s+2, \cdots, s+q-1$ 。在任何情况下, 对于新的偏移 $s^{\prime}$, 无需把 $P$ 的前 $k$ 个字符与 $T$ 中相应的字符进行比较, 因为等式 (32.6) 已经保证它们肯定匹配。

可以用模式与其自身进行比较来预先计算出这些必要的信息, 如图 32-10© 所示。由于 $T\left[s^{\prime}+1 . . s^{\prime}+k\right]$ 是文本中已经知道的部分, 所以它是字符串 $P_{q}$ 的一个后缀。可以把等式 (32.6) 解释为要求满足 $P_{k} \sqsupset P_{q}$ 的最大的 $k<q$ 。 于是, 这个新的偏移 $s^{\prime}=s+(q-k)$ 就是下一个可能的有效偏移。我们将会发现, 对每一个 $q$ 值, 把已匹配字符数目 $k$ 存储在新的偏移 $s^{\prime}$ (而不是 $s^{\prime}-s$ )中是比较方便的。

下面是预计算过程的形式化说明。已知一个模式 $P[1 \ldots m]$, 模式 $P$ 的前缀函数是函数 $\pi:\{1,2, \cdots, m\} \rightarrow\{0,1, \cdots, m-1\}$, 满足

$$\pi[q]=\max \left\{k: k<q \text { 且 } P_{k} \sqsupset P_{q}\right\}$$

即 $\pi[q]$ 是 $P$ 的最长前缀长度，且该前缀必须是 $P_{q}$ 的真后缀。又例如, 图 32-11(a)中给出了关于模式 ababaca 的完整前缀函数 $\pi$ 。

伪代码及C++实现

下面给出的 Knuth-Morris-Pratt 匹配算法的伪代码就是 KMP-MATCHER 过程。我们将看到, 其大部分都是在模仿 FINITE-AUTOMATON-MATCHER。KMP-MATCHER 调用了一个辅助程序 COMPUTE-PREFIX-FUNCTION 来计算 $\pi$ 。

$$\begin{aligned} &\begin{array}{rl} &\text {KMP-MATCHER}(T,P) \\ 1 & n=T \text {. length } \\ 2 & m=P \text {. length } \\ 3 & \pi=\text { COMPUTE-PREFIX-FUNCTION }(P) \\ 4 & q=0 & \text {// number of characters matched }\\ 5 & \text {for } i=1 \text { to } n &\text {// scan the text from left to right }\\ 6 & \quad \text {while } q>0 \text { and } P[q+1] \neq T[i] & \text {// next character does not match }\\ 7 & \quad \quad q=\pi[q] & \\ 8 & \quad \text {if } P[q+1]==T[i] & // \text { next character matches }\\ 9 & \quad \quad q=q+1 & // \text { number of characters matched + 1 } \\ 10 & \quad \text {if } q==m & // \text { is all of } P \text { matched? } \\ 11 & \quad \quad \text {print “Pattern occurs with shift” } i-m & \\ 12 & \quad \quad q=\pi[q] & // \text { look for the next match }\\ \\ &\text {COMPUTE-PREFIX-FUNCTION }(P) \\ 1 & m=P \text {. length } \\ 2 & \text {let } \pi[1 . . m] \text { be a new array } \\ 3 & \pi[1]=0 \\ 4 & k=0 \\ 5 & \text {for } q=2 \text { to } m \\ 6 & \quad \text {while } k>0 \text { and } P[k+1] \neq P[q] \\ 7 & \quad \quad k=\pi[k] \\ 8 & \quad \text {if } P[k+1]==P[q] \\ 9 & \quad \quad k=k+1 \\ 10 & \quad \pi[q]=k \\ 11 & \text {return } \pi \end{array} \end{aligned}$$

//求模式串p的next数组
ne[1] = 0;
for (int i = 2, j = 0; i <= m; ++i) {
    while (j && p[i] != p[j + 1]) j = ne[j]; //当前 [1，j] 是匹配的，长度为 j
    if (p[i] == p[j + 1]) ++j; //找到了匹配前缀，匹配长度+1；如果没找到，则ne[i]=0
    ne[i] = j;//更新, 最长匹配前后缀为+1后的j
}

//进行匹配
for (int i = 1, j = 0; i <= n; ++i){
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) ++j;
    if (j == m) {
        j = ne[j];//进行下一轮匹配
        //匹配成功后的逻辑
    }
}

这两个程序有很多相似之处, 因为它们都是一个字符串针对模式 $P$ 的匹配：KMP-MATCHER 是文本 $T$ 针对模式 $P$ 的匹配, COMPUTE-PREFIX-FUNCTION 是模式 $P$ 针对自己的匹配。

下面先来分析这两个过程的运行时间, 对其正确性的证明要复杂一些。

运行时间分析

运用摊还分析的聚合方法 (参见 $17.1$ 节) 进行分析, 过程 COMPUTE-PREFIX-FUNCTION 的运行时间为 $\Theta(m)$ 。唯一微妙的部分是表明第 $6 \sim 7$ 行的 while 循环总共执行时间为 $O(m)$ 。下 面将说明它至多进行了 $m-1$ 次迭代。我们从观察 $k$ 的值开始, 第一, 在第 4 行, $k$ 初始值为 0 , 并且增加 $k$ 的唯一方法是通过第 9 行的递增操作, 该操作在第 $5 \sim 10$ 行的 for 循环迭代中每次最 多执行一次。因此, $k$ 总共至多增加 $m-1$ 次。第二, 因为进行 for 循环时 $k<q$, 并且在 for 循环 体的每次迭代过程中, $q$ 的值都增加, 所以 $k<q$ 总成立。因此, 第 3 行和第 10 行的赋值确保了 $\pi[q]<q$ 对所有的 $q=1,2, \cdots, m$ 都成立, 这意味着每次 while 循环选代时 $k$ 的值都递减。第三, $k$ 永远不可能为负值。综合考虑这些因素, 我们会发现, $k$ 的递减来自于 while 循环, 它由 $k$ 在所 有 for 循环迭代中的增长所限定, $k$ 总共下降 $m-1$ 。因此, while 循环最多迭代 $m-1$ 次, 并且 COMPUTE-PREFIX-FUNCTION 的运行时间为 $\Theta(m)$ 。

练习 32. 4-4 要求读者通过运用类似的聚合分析, 证明 KMP-MATCHER 的匹配时间 为 $\Theta(n)$ 。

与 FINITE-AUTOMATON-MATCHER 相比, 通过运用 $\pi$ 而不是 $\delta$, 可将对模式进行预处理 1006 的时间由 $O(m|\Sigma|)$ 淢为 $\Theta(m)$, 同时保持实际的匹配时间界为 $\Theta(n)$ 。

前缀函数计算的正确性

我们稍后就会看到, 前缀函数 $\pi$ 帮助我们在字符匹配自动机中模拟转移函数 $\delta$, 但是首先我们需要证明 COMPUTE-PREFIX-FUNCTION 确实能够准确计算出前缀函数。为此, 我们将需要找到所有的前缀 $P_{k}$, 也就是给定前缀 $P_{q}$ 的真后缀。 $\pi[q]$ 的值给了我们最长的前缀, 正如在 图 32-11中所描述的, 下面的引理说明通过对前缀函数 $\pi$ 进行达代, 就能够列举出 $P_{q}$ 的真后缀的所有前缀 $P_{k}$ 。设

$$\pi^{\ast}[q]=\left\{\pi[q], \pi^{(2)}[q], \pi^{(3)}[q], \cdots, \pi^{(t)}[q]\right\}$$

其中 $\pi^{(i)}[q]$ 是按函数迭代的概念来定义的, 满足 $\pi^{(0)}[q]=q$, 并且对 $i \geqslant 1, \pi^{(i)}[q]=\pi\left[\pi^{(i-1)}[q]\right]$, 当达到 $\pi^{(t)}[q]=0$ 时, $\pi^{\ast}[q]$ 中的序列终止。

引理 32. 5(前缀函数迭代引理) 设 $P$ 是长度为 $m$ 的模式, 其前缀函数为 $\pi$, 对 $q=1,2, \cdots, m$, 有 $\pi^{\ast}[q]=\left\{k: k<q\right.$ 且 $\left.\left.P_{k}\right] P_{q}\right\}$ 。

证明 首先证明 $\pi^{\ast}[q] \subseteq\left\{k: k<q\right.$ 且 $\left.\left.P_{k}\right] P_{q}\right\}$, 或者等价地,

$$i \in \pi^{*}[q] \text { 蕴涵着 } P_{i} \sqsupset P_{q}$$

若 $i \in \pi^{\ast}[q]$, 则对某个 $u>0$, 有 $i=\pi^{(u)}[q]$ 。通过对 $u$ 进行归纳来证明式 (32. 7) 成立。对 $u=1$, 有 $i=\pi[q]$, 因为根据 $\pi$ 的定义有 $i<q$ 且 $P_{\pi [q]} \sqsupset P_{q}$, 所以此断言成立。利用关系 $\pi[i]<i$ 和 $P_{\pi[i]} \sqsupset P_i$ , 以及 $<$ 和 $\sqsupset$ 的传递性, 就可以证明对所有 $i \in \pi^{\ast}[q]$, 有 $\pi^{\ast}[q] \subseteq \{ k: \; k<q \text{ 且 } P_{k} \sqsupset P_{q} \}$ 。

下面用反证法来证明 $\left\{k: k<q\right.$ 且 $\left.P_{k} \sqsupset P_{q}\right\} \subseteq \pi^{\ast}[q]$ 。假定集合 $\left\{k: k<q\right.$ 且 $\left.P_{k} \sqsupset P_{q}\right\}-\pi^{\ast}[q]$ 是非空的, 且设 $j$ 是该集合中的最大值。因为 $\pi[q]$ 是 $\left\{k: k<q\right.$ 且 $\left.P_{k} \sqsupset P_{q}\right\}$ 中的最大值且 $\pi[q] \in \pi^{\ast}[q]$, 所以必定有 $j<\pi[q]$ 。因而可以设 $j^{\prime}$ 表示 $\pi^{\ast}[q]$ 中比 $j$ 大的最小整数。(如果 $\pi^{\ast}[q]$ 中没有其他数比 $j$ 大, 则可以选取 $j^{\prime}=\pi[q]$ ) 我们有 $P_{j} \sqsupset P_{q}$, 因为 $j \in\left\{k: k<q\right.$ 且 $\left.P_{k} \sqsupset P_{q}\right\}$, 另外因为 $j^{\prime} \in \pi^{\ast}[q]$ 和式(32.7), 有 $P_{j^{\prime}} \sqsupset P_{q}$ 。因此, 根据引理 $32.1, P_{j} \sqsupset P_{j^{\prime}}$, 而且根据此性质, $j$ 是小于 $j^{\prime}$ 的最大值。因而必定有 $\pi\left[j^{\prime}\right]=j$, 并且因为 $j^{\prime} \in \pi^{\ast}[q]$, 同样必定有 $j \in \pi^{\ast}[q]$ 。这就产生了矛盾, 所以引理得证。

算法 COMPUTE-PREFIX-FUNCTION 根据 $q=1,2, \cdots, m$ 的顺序计算 $\pi[q]$ 的值。COMPUTE-PRFFIX-FUNCTION 的第 3 行置 $\pi[1]=0$ 当然是正确的, 因为对所有的 $q$, $\pi[q] \lt q$ 。下面的引理及其推论将用于证明对 $q \gt 1$, COMPUTE-PREFIX-FUNCTION 能正确地计算出 $\pi[q]$ 。

引理 $32.6$ 设 $P$ 是长度为 $m$ 的模式, $\pi$ 是 $P$ 的前缀函数。对 $q=1,2, \cdots, m$, 如果 $\pi[q]>0$, 则 $\pi[q]-1 \in \pi^{\ast}[q-1]$ 。

证明

如果 $r=\pi[q]\gt 0$, 那么 $r \lt q \text{ 且 }P_r \sqsupset P_q$ ;

因此 $r-1\lt q-1 \text{ 且 } P_{r-1} \sqsupset P_{q-1}$

（把 $P_r$ 和 $P_q$ 中的最后一个字符去掉, 因为 $r \gt 0$, 所以这可以做到）。

因此, 根据引理 32.5，$r-1 \in \pi^{\ast}[q-1]$ 。

因此 $\pi[q]-1=r-1 \in \pi^{\ast}[q-1]$ 。

对 $q=2,3, \cdots, m$, 定义子集 $E_{q-1} \subseteq \pi^{\ast}[q-1]$ 为:

$$\begin{aligned} E_{q-1} &=\left(k \in \pi^{\ast}[q-1]: P[k+1]=P[q]\right\} \\ &=\left\{k: k<q-1, P_{k} \sqsupset P_{q-1}, P[k+1]=P[q]\right\} \quad \text { （根据引理 32.5） } \\ &=\left\{k: k<q-1, P_{k+1} \sqsupset P_{q}\right\} \end{aligned}$$

集合 $E_{q-1}$ 由满足 $\left.P_{k}\right] P_{q-1}$ 和 $P[k+1]=P[q]$ 的值 $k<q-1$ 组成, 因为 $P[k+1]=P[q]$, 所以有 $P_{k+1}\sqsupset P_{q}$ 。因此, $E_{q-1}$ 是由 $k \in \pi^{\ast}[q-1]$ 中的值组成, 可以将 $P_{k}$ 扩展到 $P_{k+1}$ 并得到 $P_{q}$ 真后缀。

推论 $32.7$ 设 $P$ 是长度为 $m$ 的模式, $\pi$ 是 $P$ 的前缀函数, 对 $q=2,3, \cdots, m$,

$$\pi[q]= \begin{cases}0 & \text { 如果 } E_{q-1}=\varnothing \\ 1+\max \left\{k \in E_{q-1}\right\} & \text { 如果 } E_{q-1} \neq \varnothing\end{cases}$$

证明 如果 $E_{q-1}$ 为空, 则没有用于扩展 $P_{k}$ 到 $P_{k+1}$ 及得到 $P_{q}$ 真后缀的 $k \in \pi^{\ast}[q-1]$ (包括 $k=0$ )。因此 $\pi[q]=0$ 。

如果 $E_{q-1}$ 为非空, 那么对每一个 $k \in E_{q-1}$, 有 $k+1<q$ 且 $P_{k+1} \sqsupset P_{q}$ 。因此, 根据 $\pi[q]$ 的定义,

$$\pi[q] \geqslant 1+\max \left\{k \in E_{q-1}\right\}$$

注意到 $\pi[q]>0$ 。设 $r=\pi[q]-1$, 那么 $r+1=\pi[q]$, 因此 $\left.P_{r+1}\right] P_{q}$ 。 因为 $r+1>0$, 所以有 $P[r+1]=P[q]$ 。而且根据引理 $32.6$, 有 $r \in \pi^{\ast}[q-1]$ 。因此, $r \in E_{q-1}$, 所以 $r \leqslant \max \{k \in$ $\left.E_{q-1}\right\}$ 或等价地,

$$\left.\pi[q] \leqslant 1+\max \left\{k \in E_{q-1}\right)\right\}$$

联合等式 (32.8) 和式 (32. 9) 即可完成证明。

现在来完成对 COMPUTE-PREFIX-FUNCTION 计算的 $\pi$ 的正确性证明。在过程 COMPUTEPREFIX-FUNCTION 中第 $5 \sim 10$ 行 for 循环的每次迭代开始时, $k=\pi[q-1]$ 。当第一次进入循环时, 该条件由第 3 行和第 4 行实现, 并且因为第 10 行的执行, 使得该条件在下面的每次选代中均保持成立。第 $6 \sim 9$ 行调整 $k$ 的值, 使它变为现在的 $\pi[q]$ 的正确值。第 $6 \sim 7$ 行的 while 循环搜索所有 $k \in \pi^{\ast}[q-1]$ 的值, 直至找到一个 $k$ 值, 使得 $P[k+1]=P[q]$; 此时, $k$ 是集合 $E_{q-1}$ 中的最大值, 根据推论 $32.7$, 可以置 $\pi[q]$ 为 $k+1$ 。如果找不到这样的值, 则在第 8 行 $k=0$ 。如果 $P[1]=P[q]$, 那么应该将 $k$ 和 $\pi[q]$ 都设置为 1 ; 否则, 只需将 $\pi[q]$ 置为 0 而不管 $k_{\circ}$ 第 $8 \sim 10$ 行完成在任意条件下 $k$ 和 $\pi[q]$ 的设置。这样就完成了对 COMPUTE-PREFIX-FUNCTION 正确性的证明。

KMP算法的正确性

过程 KMP-MATCHER 可以看做是过程 FINITE-AUTOMATON-MATCHER 的一次重新实现, 但是却用到了前缀函数 $\pi$ 来计算状态转换。特别地, 我们将证明在 KMP-MATCHER 和 FINITE-AUTOMATON-MATCHER 的 for 循环的第 $i$ 次迭代时, 当检测 $m$ 的等效性时, 两个过程的状态 $q$ 的值相同(KMP-MATCHER 在第 10 行, FINITE-AUTOMATON-MATCHER 在第 5 行)。一旦证明了 KMP-MATCHER 模拟了 FINITE-AUTOMATON-MATCHER 的操作过程, 自然也就可以由 FINITE-AUTOMATON-MATCHER 的正确性推出 KMP-MATCHER 也是正确

在我们正式证明 KMP-MATCHER 模仿 FINITE-AUTOMATON-MATCHER 之前, 让我们来理解前缀函数 $\pi$ 如何代替转移函数 $\delta$ 。回顾一下, 当字符串匹配自动机处在状态 $q$ 时, 它扫描到字符 $a=T[i]$, 然后移动到一个新的状态 $\delta(q, a)$ 。如果 $a=P[q+1]$, 那么 $a$ 将持续对模式进行匹配, $\delta(q, a)=q+1$; 否则, $a \neq P[q+1]$, 那么 $a$ 就终止了对模式的匹配, 并且 $0 \leqslant \delta(q, a)$ $\leqslant q$ 。在第一种情况下, 当 $a$ 持续匹配时, KMP-MATCHER 移动到状态 $q+1$ 而无需参考 $\pi$ 函数：在第 6 行的 while 循环检测第一次报错，在第 8 行检测结果为真，并且在第 9 行 $q$ 增加。

当 $a$ 不能持续进行模式匹配时, $\pi$ 函数开始起作用, 因此新的状态 $\delta(q, a)$ 要么是 $q$, 要么是沿着自动机移动的 $q$ 的左边状态。在 KMP-MATCHER 中第 $6 \sim 7$ 行的 while 循环迭代通过状态 $\pi^{\ast}[q]$, 要么停在一个 $q^{\prime}$ 状态, 使得 $a$ 和 $P\left[q^{\prime}+1\right]$ 匹配, 要么是 $q^{\prime}$ 已经走完变为了 0 。如果 $a$ 和 $P\left[q^{\prime}+1\right]$ 匹配，那么第 9 行就进入新的状态 $q^{\prime}+1$ ，这应该等价于准确模拟 $\delta(q, a)$ 的工作。换句话说，新状态 $\delta(q, a)$ 要么处于状态 0 ，要么处于比某些在 $\pi^{\ast}[q]$ 中更高的状态。

让我们来考虑图 32-7 和图 32-11 中的例子, 其中模式为 $P=\mathrm{ababaca}$ 。假设自动机处在 $q=5$ 的状态; 这些在 $\pi^{\ast}[5]$ 中的状态是以 3,1 和 0 的顺序递减的。如果下一个扫描到的字符是 $c$, 那 么很容易看到自动机移动到状态 $\delta(5, c)=6$, 在 KMP-MATCHER 和 FINITE-AUTOMATONMATCHER 中都是如此。现在假设下一个扫描到的字符是 b, 那么自动机会移动到 $\delta(5, \mathrm{~b})=4$ 状态。在 KMP-MATCHER 中每次退出 while 循环都运行第 7 行一次, 并且到达状态 $q^{\prime}=\pi[5]=3$ 。 由于 $P\left[q^{\prime}+1\right]=P[4]=\mathrm{b}$, 第 8 行检测结果是真, 并且 KMP-MATCHER 移动到新的状态 $q^{\prime}+1=4=\delta(5, \mathrm{~b})$ 。最后，假设下一个扫描到的字符是 $\mathrm{a}$ ，那么自动机就自动移动到状态 $\delta(5,a)=1$ 。在第 6 行执行前三次检测, 结果是真。第一次我们发现 $P[6]=\mathrm{c} \neq \mathrm{a}$ 并且 KMPMATCHER 移动到状态 $\pi[5]=3$ (处在 $\pi^{\ast}[5]$ 中的第一个状态), 第二次我们发现 $P[4]=\mathrm{b} \neq \mathrm{a}$ 并且移动到状态 $\pi[3]=1$ (处在 $\pi^{\ast}[5]$中的第二个状态), 第三次我们发现 $P[2]=\mathrm{b} \neq \mathrm{a}$ 并且移动到 状态 $\pi[1]=0$ (处在 $\pi^{\ast}[5]$ 中的最后一个状态)。一旦到达状态 $q^{\prime}=0$, while 循环就退出。现在, 在第 8 行发现 $P\left[q^{\prime}+1\right]=P[1]=\mathrm{a}$, 并且在第 9 行移动自动机到新的状态 $q^{\prime}+1=1=\delta(5, \mathrm{a})$ 。

因此, 我们了解到 KMP-MATCHER 通过以递减的顺序在状态 $\pi^{\ast}[q]$ 中迭代循环, 在某些状态 $q^{\prime}$ 停止, 然后可能移动到状态 $q^{\prime}+1$ 。尽管似乎在模拟计算 $\delta(q$, a) 时有很多工作要做, 但是从渐近意义上看, KMP-MATCHER 并不比 FINITE-AUTOMATON-MATCHER 慢。

我们现在准备正式证明 Knuth-Morris-Pratt 算法的正确性。根据定理 32.4, 在每次运行 FINITE-AUTOMATON-MATCHER 的第 4 行时得到 $q=\sigma\left(T_{i}\right)$ 。因此, 它足以证明 for 循环在 KMP-MATCHER 中有同样的特性。通过对循环迭代次数进行归纳来证明。首先, 当它们第一次进入各自的 for 循环时, 程序都是预设 $q=0$ 。考虑在 KMP-MATCHER 中对 $i$ 迭代的 for 循环, 假设 $q^{\prime}$ 是该循环迭代的初始状态。通过归纳假设, 我们可以得到 $q^{\prime}=\sigma\left(T_{i-1}\right)$ 。需要证明在第 10 行也有 $q=\sigma\left(T_{i}\right)$ 。（我们将又一次分开处理第 12 行。 $)$

当考虑到字符 $T[i]$ 时, $P$ 的最长前缀也是 $T_{i}$ 的一个后缀, 要么是 $P_{q^{\prime}+1}$ (如果 $P\left[q^{\prime}+1\right]=T[i]$ ), 要么是 $P_{q^{\prime}}$ 的某个前缀 (这并不一定为真前缀, 并且可能为空)。我们分别考虑以下三种情况: $\sigma\left(T_{i}\right)=0, \sigma\left(T_{i}\right)=q^{\prime}+1$ 和 $0<\sigma\left(T_{i}\right) \leqslant q^{\prime}$ 。

• 如果 $\sigma\left(T_{i}\right)=0$, 那么 $P_{0}=\varepsilon$ 是 $P$ 的唯一前缀, 也是 $T_{i}$ 的一个后缀。第 $6 \sim 7$ 行的 while 循环迭代 $\pi^{\ast}\left[q^{\prime}\right]$ 中的值, 尽管 $P_{q} \sqsupset T_{i-1}$ 对每个 $q \in \pi^{\ast}\left[q^{\prime}\right]$ 都成立, 但是循环绝不会找到一个使得 $P[q+1]=T[i]$ 的 $q$ 。当 $q=0$ 时, 循环结束, 并且第 9 行自然就不执行了。因此, 在第 10 行 $q=0$, 使得 $q=\sigma\left(T_{i}\right)$ 。
• 如果 $\sigma\left(T_{i}\right)=q^{\prime}+1$, 那么 $P\left[q^{\prime}+1\right]=T[i]$, 并且第一次检测第 6 行的 while 循环失败。 执行第 9 行, $q$ 增加, 使得 $q=q^{\prime}+1=\sigma\left(T_{i}\right)$ 。
• 如果 $0<\sigma\left(T_{i}\right) \leqslant q^{\prime}$, 那么第 $6 \sim 7$ 行的 while 至少循环迭代一次, 对于每一个值 $q \in \pi^{\ast}[q]$, 以递减顺序进行检测, 直到 $q<q^{\prime}$ 时停止。因此, $P_{q}$ 是 $P_{q}$ 满足 $P[q+1]=T[i]$ 的最长前缀, 使得当 while 循环终止时, $q+1=\sigma\left(P_{q^{\prime}} T[i]\right)$ 。由于 $q^{\prime}=\sigma\left(T_{i-1}\right)$, 由引理 $32.3$ 可以 导出 $\sigma\left(T_{i-1} T[i]\right)=\sigma\left(P_{q^{\prime}} T[i]\right)$ 。因此有

$$q+1=\sigma\left(P_{q^{\prime}} T[i]\right)=\sigma\left(T_{i-1} T[i]\right)=\sigma\left(T_{i}\right)$$

当 while 循环终止时, 在第 9 行的 $q$ 增加之后, 得到 $q=\sigma\left(T_{i}\right)$ 。

在 KMP-MATCHER 中, 之所以一定要有第 12 行代码, 是为了避免在找出 $P$ 的一次出现后, 第 6 行中可能出现 $P[m+1]$ 的情形。（由练习 32. 4-8 的提示, 即对任意 $a \in \sum, \delta(m, a)=$ $\delta(\pi[m], a)$, 或者等价地, $\delta(P a)=\delta\left(P_{\pi m]} a\right)$, 可以推得在下一次执行第 6 行代码时, $q=$ $\sigma\left(T_{i-1}\right)$ 依然保持有效。 $)$ 关于 Knuth-Morris-Pratt 算法的正确性证明, 其余的部分可以从 FINITEAUTOMATON-MATCHER 的正确性推得, 因为现在可以看出 KMP-MATCHER 模拟了 FINITE-AUTOMATON-MATCHER 的操作过程。

综合运用

1052. 设计密码（字符串匹配自动机 + KMP）

题目描述

你现在需要设计一个密码 $S$，$S$ 需要满足：

• $S$ 的长度是 $N$；
• $S$ 只包含小写英文字母；
• $S$ 不包含子串 $T$；

例如：$abc$ 和 $abcde$ 是 $abcde$ 的子串，$abd$ 不是 $abcde$ 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 $10^9+7$ 的余数。

输入格式

第一行输入整数N，表示密码的长度。

第二行输入字符串T，T中只包含小写字母。

输出格式

输出一个正整数，表示总方案数模 $10^9+7$ 后的结果。

数据范围

$1 \le N \le 50$,
$1 \le |T| \le N$，$|T|$是$T$的长度。

输入样例1：

2
a 

输出样例1：

625 

输入样例2：

4
cbc 

输出样例2：

456924 

算法分析

f[i][j]：生成了 i个密码，且状态停留在 j，即有限自动机读入了 i个字符，且$\phi(T_i)=j$

状态 j也表示已成功匹配 j个字符

算法流程：

• 循环生成密码字符个数，正在生成第 i个字符
• 枚举生成 i - 1个密码字符后，所停留的状态 $\phi(T_{i-1})=j$
• 枚举正在生成的是什么字符，$T[i] = a \sim z$
• 计算状态转移，求 $\phi(T_i) = \delta(j,T[i])$ ，转移函数用KMP算法的前缀函数 $\pi()$ 来实现
• 状态转移从 j到 q，更新计算 f[i][q]的方案数
• 计算最终所有方案数，生成完 n个密码字符，且状态不停留在 m的方案都满足条件，累加起来

Solution

#include <iostream>
using namespace std;
const int N = 60, mod = 1e9 + 7;
int f[N][N], ne[N];
int main() {
  int n;
  cin >> n;
  string p;
  cin >> p;
  int m = p.size();
  p = " " + p;
  
  for (int i = 2, j = 0; i <= m; ++i) {
    while (j > 0 && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) ++j;
    ne[i] = j;
  }
  
  f[0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < m; ++j) {//枚举处理前i - 1个字符后停留的状态
      for (char c = 'a'; c <= 'z'; ++c) {
        int q = j;
        while (q > 0 && c != p[q + 1]) q = ne[q];
        if (c == p[q + 1]) ++q;
        if (q < m) f[i][q] = (f[i][q] + f[i - 1][j]) % mod;
      }
    }
  }
  
  int ans = 0;
  for (int j = 0; j < m; ++j) ans = (ans + f[n][j]) % mod;
  cout << ans;
}