最近跟着《算法导论》看了 KMP 算法一节，在此记录下自己的所写所想。其实自己之前看过一遍，也对着书上的代码敲过一遍，更甚者抄了一遍公式推导。然而还是看完即忘，表面上的原因很简单，大家都会说没彻底弄懂当然会忘记。之后我在思考为什么会懂不了。

记不得在哪本书的前言看到过类似的前言：为了不吓到缺乏数学功底的学生，只有万不得已的时候才引入数学，平时都尽量采用直观、符合直觉的说法。我觉得这边 直觉 二字非常重要，虽然有时候直觉可能出错，但往往是解决问题的突破口，并且由于是直觉，所以忘记不了。

接下来的正文我尝试直觉加上证明的方式阐述 KMP 算法。和《算法导论》里一样，先了解字符串匹配自动机的思想，接着就能很自然的过渡到 KMP 的思想。

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

首先了解一下有限自动机的定义。一个有限自动机\(M\)是一个 5 元组\((Q,q_{0},A,\varSigma,\delta)\)，其中：

●    \(Q\) 是状态的有限集合。

●    \(q_0\in Q\) 是初始状态。

●    \(A\subseteq Q\) 是一个特殊的接受状态集合。

●    \(\varSigma\) 是有限输入字母表。

●    \(\delta\) 是一个从 \(Q\times\varSigma\) 到 \(Q\) 的函数，成为 \(M\) 的转移函数。

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

有限自动机 \(M\) 引入了一个函数 \(\phi\)，称为终态函数，它是从 \(\varSigma^*\) 到 \(Q\) 的函数，满足 \(\phi(\omega)\) 是 \(M\) 在扫描字符串 \(\omega\) 后终止时的状态。因此，当且仅当 \(\phi(\omega)\in A\) 时，\(M\) 接受字符串 \(\omega\)。我们可以用转移函数递归定义 \(\phi\) ：

\(\phi(\varepsilon)=q_0\)
\(\phi(\omega a)=\delta(\phi(\omega),a),\ \ \omega \in \varSigma^*,a\in\varSigma\)

状态自动机定义不复杂，我对上述定义做一个自己理解的通俗描述。如图 1 所示，就是一个简单的状态自动机，它有两个状态：0 和 1。0 和 1 状态的切换根据当前状态加上输入的字符可以进行转移。黑色结点表示终态，一个字符最终落到 1 状态才表示接受，由此可以知道这个状态自动机接受那些以奇数个 a 结尾的字符串。

上面的自动机概念已经够用了，现在把目光重新放在“如何利用有限自动机处理字符串匹配”这个问题上面来。对照上述定义的自动机 5 元组，一个急需要确定的是状态是什么。我觉得确定状态应该是最难的一个问题，不首先解决这个问题，就会导致不能理解后续的算法。《算法导论》里给出了这个状态的定义：当前输入字符串的后缀等于待匹配模式前缀的最长长度。

设 \(P\) 为给定的模式。函数 \(\sigma\) 是一个从 \(\varSigma^*\) 到 \(\{0,1,\cdots,m\}\) 上的映射，满足 \(\sigma(x)\) 是 \(x\) 的后缀 \(P\) 的最长前缀的长度：

\( \sigma(x)=max\{k : P_{k} \sqsupset x\} \)

在了解定义的这个状态后，还是比较能理解，并且很容易会往转移函数上想：\(\delta(q,a)=\sigma(xa)\)。这个式子的意思是说，当前的状态是 \(q\)，并且接收了一个字符 \(a\)，那么之后变到的状态就是之前的字符串 \(x\) 接收了 \(a\) 字符后整个字符串的状态 \(\sigma(xa)\)；当 \(q\) 等于 \(P\) 的长度时，达到终态，即字符串匹配上了。以上想法过于直观，好像也没有看到书上有特别给出个引理证明，大致的思路就是：每当输入一个接收一个新字符，就重新计算当前字符串后缀等于模式前缀的最长长度，一旦相等就算匹配上了。

状态定义好了，但是 \(\sigma(xa)\) 转移函数看着有点问题，要用到整个字符串 \(x\)，想想觉得这个转移函数只能“实时”的计算出来了？想到这里，就发现跟上了书中的思路，因为其中给出了这么一个关系式：

\( \sigma(xa)=\sigma(P_q a) \)

上述这个式子无疑“雪中送炭”，它代表你不用在乎整个字符串 \(x\)，而 \(P\) 是事先已知的，就可以根据 \(P\) 提前计算出转移函数！上面这个式子直观上也很容易理解，为什么 \(x\) 中只使用 \(P_q\) 部分就行了呢，万一还要使用再往前的字符呢？因为状态定义了 \(q\) 是 \(x\) 的后缀等于 \(P\) 前缀的最大长度，那么接收字符 \(a\) 之后，新的状态最大就只可能是 \(q+1\)，即最新的这个字符也匹配上了。如何新的状态 \(q^\prime \ge q+1\)，那么跟 \(q\) 的定义就矛盾了，它不是最大的。下面抄录书中的详细证明。

引理 32.2 （后缀不等式） 对任意字符串 \(x\) 和 字符 \(a\)，\(\sigma(xa)\le\sigma(x)+1\)。

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

引理 32.3 （后缀函数递归引理） 对任意 \(x\) 和字符 \(a\)，若 \(q=\sigma(x)+1\)，则 \(\sigma(xa)=\sigma(P_q a)\)。

证明 根据 \(\sigma\) 的定义，有 \(P_q \sqsupset x\)。如图 3 所示，有 \(P_{q}a \sqsupset xa\) ,并由引理 32.2 知，\(r \le q+1\)。因此可得 \(\lvert P_r \rvert = r \le q+1 = \lvert P_qa \rvert \)。因为 \(P_qa \sqsupset xa\) 和 \(P_r \sqsupset xa\) 并且 \(\lvert P_r \rvert \le \lvert P_qa \rvert\)，所以可知 \(P_r \sqsupset P_qa\)。因此可得 \(r \le \sigma(P_qa)\)，即 \(\sigma(xa)\le\sigma(P_q a)\)。但由于 \(P_qa \sqsupset xa\)，所以有 \(\sigma(P_q a)\le\sigma(xa)\)，从而证明 \(\sigma(xa)=\sigma(P_q a)\)。

至此，字符串匹配自动机的 5 元组都已经“准备妥当”。\(Q\) 是目前接收字符串后缀等于待匹配字符串前缀的最大长度，为\(\{0,1,\cdots,\lvert P \rvert\}\)；\(q_0 = 0\)；\(A,\varSigma\) 视具体情况而定；\(\delta\) 就是前面重点讲的 \(\sigma\) 函数，以及 \(\sigma(xa)=\sigma(P_q a)\)。下面给出字符串匹配自动机的伪代码，相应的 C 代码见附录。

首先是自动机的基本模板，初始状态为 0，接着接收各个新的字符，并更新状态。如果某次状态更新为待匹配字符串的某个长度，则达到了终态，打印给予提示。这边需要注意的是，即便是中途到达了终态，也不必终止自动机，状态的改变在终态上仍然是成立的，定义非常统一。

FINITE-AUTOMATON-MATCHER\((T,\delta,m)\)
1\(n=T.length\)
2\(q=0\)
3for \(i=0\) to \(n\)
4\(q=\delta(q,T[i])\)
5if \(q==m\)
6print "Pattern occurs with shift" \(i-m\)

接着就是转移函数的生成了，从前面的证明得知可以直接使用模式 \(P\) 生成转移函数，只需穷尽所有状态后面跟着的所有字符，算出 \(\sigma\) 函数的结果即可。这边同样需要注意的是，终态上的转移也是成立的，需要特别考虑到。

COMPUTE-TRANSITION-FUNCTION\((P,\varSigma)\)
1\(m = P.length\)
2for \(q=0\) to \(m\)
3for each charater \(a \in \varSigma\)
4\(k=min(m+1,q+2)\)
5repeat
6\(k = k -1\)
7until \(P_k \sqsupset P_qa\)
8\(\delta(q,a)=k\)
9return \(\delta\)

由上面的伪代码，容易得到运行时间为 \(O(m^3\varSigma)\)，当模式字符串很大，甚至和匹配的字符串差不多时，就会变得比暴力搜索更差。接下来来看看 KMP 算法是如何优化字符串匹配自动机的。

2. Knuth-Morris-Partt 算法

字符串匹配自动机耗时的原因，可以把它看成是一个穷举的过程，所有的状态后面加上任意的字符的情况都提前计算好了，肯定会慢，同时占用大量空间。结合附录里面的代码 1 ，考虑如果不管新接收的字符 \(a\)，假设字符 \(a\) 匹配，那么后续的匹配内容就是模式 \(P\) 本身，即 \(P\) 后缀等于真前缀的最长长度（自身肯定匹配自身），这个定义和 \(\sigma\) 函数类似，书上定义为 \(\pi\) 函数，满足

\(\pi(q)=max\{k:k\lt q 且 P_k \sqsupset P_q\}\)

在获得了 \(\pi\) 函数，可以思考一下如何获得自动机里定义的 \(\delta\) 函数。因为只要计算出了 \(\delta\) 函数，那么就满足字符串匹配自动机的定义，算法自然正确。

考虑以下场景，在某一状态 \(q\) 下面，已经知道了所有状态下 \(\pi\) 函数的值：如果新接收的字符串 \(a\) 和 \(P[q+1]\) 匹配，那么状态自然更新到 \(q+1\)，那么如果不匹配呢？那么可以利用 \(\pi(q)\) 的值，判断 \(P[\pi(q)+1]\) 和字符 \(a\) 是否匹配（这个原先自动机匹配的思路非常相似），如果匹配，那么状态更新到 \(\pi(q)+1\)，那如果又不匹配么？因为前后缀相等，并且 \(\pi\) 函数定义的是最长真前缀，那么后缀等于最长真前缀的搜索范围就又落到了 \(P[1\cdots\pi(q)]\)（下标从 1 开始），这时候出现了一个递归子问题，我们可以求得 \(\pi(\pi(q))\) 来求解。如果又不匹配，则求得 \(\pi(\pi(\pi(q)))\)，以此类推。以上就是 KMP 算法的“白话”版本，KMP 算法通过 \(\pi\) 函数 尝试 多次求得 \(\delta\) 函数。

\(\pi\) 函数尝试计算的最终结果与 \(\delta\) 函数是等价的证明，即 KMP 算法的正确性证明，《算法导论》里面有单独的一小节说明，这边不再给出。但书中有两个引理和一个推论介绍如何求 \(\pi\) 函数，其实思路和上段文字的思路非常相似，只不是字符串匹配是模式 \(P\) 和 字符串\(x\) 之间的计算，而计算 \(\pi\) 函数是模式 \(P\) 和 \(P\) 本身之间的计算。下面将引理和推论抄录（证明过程省略），以此感受 \(\pi\) 函数的计算方法和 KMP 算法的正确性。

设

\(\pi^*[q]=\{\pi[q],\pi^{(2)}[q],,\pi^{(3)}[q],\cdots,\pi^{(t)}[q]\}\)

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

引理 32.5 （前缀函数迭代引理） 设 \(P\) 是长度为 \(m\) 的模式，其前缀函数为 \(\pi\)，对 \(q=1,2,\cdots,m\)，有 \(\pi^*[q]=\{k:k \lt q 且 P_k \sqsupset P_q\}\)。

引理 32.6 设 \(P\) 是长度为 \(m\) 的模式，\(pi\) 是 \(P\) 的前缀函数。对 \(q=1,2,\cdots,m\)，如果 \(\pi[q]\gt0\)，则 \(\pi[q]-1 \in \pi^*[q-1]\)。

对 \(q=2,3,\cdots,m\)，定义子集 \(E_{q-1} \subseteq \pi^*[q-1]\) 为：

\(E_{q-1}=\{k \in \pi^*[q-1]:P[k+1]=P[q]\}\)
\(=\{k:k \lt q-1,P_k \sqsupset P_{q-1},P[k+1]=P[q]\}\)
\(=\{k:k \lt q-1,P_{k+1} \sqsupset P_{q}\}\)

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

\(\pi[q]=\left\{ \begin{array}{ll} 0 & 如果 E_{q-1}=\varnothing \\\\ 1+max\{k \in E_{q-1}\} & 如果 E_{q-1} \ne \varnothing \end{array} \right.\)

从推论 32.7 的式子可以看出，求 \(\pi\) 函数的过程和 动态规划 非常类似，可以用动态规划的思路来理解。引理 32.5 说明 \(P_q\) 的全部后缀和 \(\pi^*[q]\) 是等价的，这个引理的通俗理解在之前说明过，因为 \(\pi[q]\) 的定义的是最大的前缀，并且条件是和后缀相等，“相等”和“最大”就可以把第二小的前缀缩小到 \(\pi[q]\) 这个范围，即等于 \(\pi[\pi[q]]\)，以此类推。引理 32.6 说明，\(\pi[q]\) 可以根据 \(\pi^*[q-1]\) 计算出来，这个引理比较好理解，\(\pi[q]\) 的前提就是 \(P_{q-1}\) 的某一前缀的下一字符等于 \(P[q]\)，而 \(\pi^*[q-1]\) 代表了 \(P_{q-1}\) 所有前缀，自然是可以推导出来的。基于两个引理，可以很自然的写出类似动态规划的转移方程，如果 \(\pi^*[q-1]\) 中没有下一字符等于 \(P[q]\)，那么自然 \(\pi[q]=0\)；如果有的话，那就是其中最长的，并加上匹配上的字符（+1）。比较容易理解 \(\pi\) 函数的迭代结果是递减的，所以实际中不用求出 \(\pi^*[q-1]\) 中全部的元素，迭代过程中第一次匹配上的即为想要的结果。

至此 KMP 算法的内容就梳理完毕了，下面给出 KMP 算法的匹配过程以及 \(\pi\) 函数的生成过程。

首先是 KMP 算法的匹配过程，和字符串匹配自动机一样，\(q\) 代表当前的状态，当 \(q\) 等于模式长度时达到终态。与字符串匹配自动机不一样的是，KMP 算法的转移函数是根据 \(\pi\) 前缀函数算出来的，只要最新接收的字符没匹配上就迭代 \(\pi\) 函数，从而计算出最新的状态。这边需要说明的一下是，代码第 12（B） 行，书中没有缩进，应该是错误了。结尾再次更新状态会导致匹配的长度减少，举一个反例就能证明，如果模式是 \(aaaa\)，目前 \(q=3\)，那么再次迭代前缀函数的时候 \(q=2\)，如果下次接收的字符还是 \(a\)，那么就错过了匹配机会。当已经达到终态时，下一次匹配就不可能在原有状态上继续匹配了，所以需要更新状态，为下次匹配做准备。

KMP-MATCHER\((T,P)\)
1\(n = T.length\)
2\(m = P.length\)
3\(\pi=\)COMPUTE-PREFIX-FUNCTION(\(P\))
4\(q=0\)
5for \(i=0\) to n
6while \(q\gt0\) and \(P[q+1] \ne T[i]\)
7\(q=\pi[q]\)
8if \(P[q+1] == T[i]\)
9\(q=q+1\)
Aif \(q==m\)
Bprint "Pattern occurs with shift" \(i-m\)
C\(q=\pi[q]\) //这句应该是书上写错了？

接下来是 \(\pi\) 后缀函数的生成过程。可以看到 \(\pi\) 函数的生成过程和匹配过程非常相似，只不过是 \(\pi\) 函数基于模板 \(P\) 自身的匹配。然而还是有些地方需要特别注意的，后缀函数的生成过程中有两个变量，一个是 \(q\)，因为要计算每个状态对应的 \(\pi[q]\)，因为 \(\pi\) 针对的真后缀，所以 \(\pi[1] = 0\)；另一个变量 \(k\) 就有点讲究了，它充当上一次结果的记录，同时也控制着必须在有真前缀的前提下才进行匹配。

COMPUTE-PREFIX-FUNCTION\((P)\)
1\(m = P.length\)
2let \(\pi[1\cdots m]\) be a new array
3\(\pi[1]=0\)
4\(k=0\)
5for \(q=2\) to m
6while \(k\gt 0\) and \(P[k+1] \ne P[q]\)
7\(k=\pi[k]\)
8if \(P[k+1] == P[q]\)
9\(k=k+1\)
A\(\pi[q]=k\)
Breturn \(\pi\)

最后还剩下的是 KMP 算法的时间复杂度和空间复杂度的分析。空间复杂度为 \(\lvert P \rvert\)，比自动状态机节省，时间复杂度书中说是 \(O(n)\)，这边留作后续研究。直观上的感受，虽然状态转移是实时算的，但是对于大部分情况下的字符串，\(\pi\) 后缀函数的迭代应该很快就会“收敛”到 0。

3. 总结和思考

上述对字符串匹配自动机和 KMP 算法进行了梳理，可以看出 KMP 算法可以依托字符串匹配自动机的“设计理念”。自以为，字符串匹配自动机方面，状态的定义是关键，状态定义为当前字符串的后缀等于模式字符串的前缀的最大长度，当其等于模式字符串的长度时达到终态。自动机是对 (状态 \(\times\) 字符) 的穷举遍历，而 KMP 算法是根据必须首先要满足的模式自身前后缀相等的最大长度，实时计算出自动机的转移函数。而模式自身前后缀相等的最大长度，即 \(\pi\) 后缀函数，具有良好的性质，\(\pi[q]\) 和 \(\pi^*[q-1]\) 相关，从而能采用类似动态规划的算法依次计算得出。

还有一点思考和前言里讲的类似，数学公式便于浓缩抽象，原本需要大段话描述的内容一个符号或者函数就能代替，还有就是非常准确，记号都是规定好的，没有二义性。但是数学公式行间，难免会把一些直观或者“灵感”之类的东西都给抹去了，直觉可能出错，所以需要证明，但是感觉之前的学习往往忽略了直觉的捕捉，这一点后续的学习要多加注意。

同时还有一些“工程”和“学术”上的思考，两者学习套路似乎有点相背，拿 Linux 驱动和 KMP 算法的学习作比较：Linux 驱动的学习似乎是多实践，入门阶段多思考也没有用，框架就在那里，思考不出什么花样出来；而 KMP 算法的学习是多思考，入门阶段多实践也没有用，思想都没弄懂，乱调代码也没有任何意义。就目前自己的水平，想的太多，难免眼高手低，自己不是搞算法的，自然“学了没用”，工资难涨；做的太多，又避免不了重复呆板，忽略了思考，自我感觉不太好，又觉得不利于长远发展。“想”往往会让我产生惰性，今后要多花一些时间在动手上，在实践学科上，并做好“思考”的兼顾。

附录 Leetcode 28

这边以 Leetcode 28 作为练手，实现一下学习的 KMP 算法。题目的描述如下所示，可以看到就是一道“裸”的字符串匹配题目。

首先编写一下第 1 节自动机的实现，如代码 1 和图 3 所示，自动机的基础框架实现没什么困难，主要是转移函数的生成需要特别注意一下下标。可以画一张图辅助一下思路，如图 3 所示，可以先尝试匹配字符 a，接着按下标 i 和 j 依次匹配，并且需要注意一下 k 可能会出现超出模式长度的情况。

1. int delta[10000][256];
2.  
3. void ComputeTransition(string& P)
4. {
5.     int q;
6.     int a;
7.     int k, i, j;
8.  
9.     for (q = 0; q <= P.length(); q++)
10.     {
11.          for (a = 0; a <= 0xff; a++)
12.          {
13.              k = q + 1;
14.              if (k > P.length())
15.                   k = P.length();
16.  
17.              while (k)
18.              {
19.                   i = k - 1;
20.                   if (P[i] == a)
21.                   {
22.                       for (i--, j = q - 1; i >= 0 && P[i] == P[j]; i--, j--);
23.                   }
24.                   if (i < 0)
25.                       break;
26.                   else
27.                       k--;
28.              }
29.  
30.              delta[q][a] = k;
31.          }
32.     }
33. }
34.  
35. int strStr(string haystack, string needle)
36. {
37.     if (needle.length() == 0)
38.          return 0;
39.  
40.     ComputeTransition(needle);
41.  
42.     int q = 0;
43.     int i;
44.     for (i = 0; i < haystack.length(); i++)
45.     {
46.          q = delta[q][haystack[i]];
47.          if (q == needle.length())
48.              break;
49.     }
50.  
51.     if (q == needle.length())
52.          return (i - q + 1);
53.     else
54.          return -1;
55. }

然而，这种方法超时了，超时的样例是重复字符特别多，并且搜索字符串和模式字符串都很大。在这种情况下，转移函数的建立变得比暴力方法所需的时间更高。所以再尝试一下 KMP 算法。

KMP 算法的实现如代码 2 所示，了解了正文部分对 \(\pi\) 后缀函数的定义后，实现起来会比字符串匹配自动机容易一点，代码量也少了一些。需要注意的是，这边和代码 1 一样，都是匹配即可，匹配直接 break 出来，不再更新后续状态。在之前超时的重复字符特别多的样例下面，KMP 算法“退化”到和暴力算法一样，并且增加了后缀函数的计算时间，但是总的时间复杂度是一样的，所以通过了。

1. int pi[100000];
2.  
3. void ComputePrefixFunction(string& P)
4. {
5.     int q;
6.     int k;
7.  
8.     pi[1] = 0;
9.     k = 0;
10.     for (q = 2; q <= P.length(); q++)
11.     {
12.          while (k > 0 && P[k] != P[q - 1])
13.              k = pi[k];
14.          if (P[k] == P[q - 1])
15.              k++;
16.          pi[q] = k;
17.     }
18. }
19.  
20. int strStr(string haystack, string needle)
21. {
22.     if (needle.length() == 0)
23.          return 0;
24.  
25.     ComputePrefixFunction(needle);
26.  
27.     int q = 0;
28.     int i;
29.  
30.     for (i = 0; i < haystack.length(); i++)
31.     {
32.          while (q > 0 && needle[q] != haystack[i])
33.              q = pi[q];
34.          if (needle[q] == haystack[i])
35.              q++;
36.          if (q == needle.length())
37.              break;
38.     }
39.  
40.     if (q == needle.length())
41.          return (i - q + 1);
42.     else
43.          return -1;
44. }