Wisdom in the mind is better than money in the hand.

一、引言

1.1 反馈之殇

  今年年初的时候，组内接到个反馈，客户很早之前购买的咱们公司的一款产品系统无法正常启动。公司经初步排查后确定故障原因是由于咱们应用识别模块占用的内存偏高，而这款产品又属于比较老的型号，硬件配置较低，启动时内存不足引起的。
  我们经过深入分析发现，导致应用识别模块内存占用率居高不下的一个主要原因是AC引擎的具体代码实现上有些问题，有很大的优化空间。经过重新设计和实现后，单class内存占用率直接降低了100多M，整个class（还包含其它很多模块）才占用内存约600M，效果可以说还是相当显著的。
  深入排查的时候，少不了要去过N遍引擎代码，而AC多模匹配算法自然也成了我们的重点关注对象。经过我们不懈的努力，最终解决了这个问题，在此分享出来，以供大家参考。

1.2 系列文章

  其实最开始的时候并没有想写成系列的文章，因为后续的引擎演进会迁移到其它更高效的字符串匹配算法上，因此我们决定把一些常见/常用的字符串匹配算法都分享出来，方便对这方面感兴趣的同学学习了解，同时也作为我们组的一种技术积累，欢迎大家积极跟我们探讨交流。

1.3 前注

  本系列文章的目标是让没有任何字符串匹配/算法背景的同学也能轻松理解，在行文上可能会丧失一定的专业和简洁性，如有不妥，请多多指正。

二、字符串匹配算法

2.1 简介

  字符串匹配算法自提出至今，可以说是硕果累累。无数业界大佬前赴后继的投入到了算法的研究中。时至今日，已经有大量成熟的匹配算法（及其变异体），对这些算法我们总结出一张概览表如下所示（仅仅覆盖了大部分算法）：

  注：表格中仅仅列出了一些Paper能找到的算法，其它的则没有在此列出。

2.2 术语&&约定

  为了尽量保持语言的简洁，我们在此对一些术语及约定做一个介绍。

2.2.1 目标串

  给定一串字符，比如”Sometimes, the everlasting hate have no unique period.”，我们要在这串字符里面寻找某个/某些单词/字母，我们称这串字符为目标串(Text)，其长度记为$n$，指向目标串的索引变量我们用$r,\ r=1,2,3,…,n$表示。
  即$t_r$表示目标串的第$r$个字符，目标串为：$Text = t_1 t_2 t_3 … t_r …t_n$。

2.2.2 特征串

  接上面说的，我们要寻找的某个/某些单词/字母（比如我要找”unique”），我们称之为特征串(Pattern)，其长度记为$m$，指向特征串的索引变量我们用$s, \ s=1,2,3,…,m$表示。
  即$p_s$表示特征串的第$s$个字符，特征串为：$Pattern = p_1 p_2 p_3 … p_s … p_m$。

2.3 Naive Algorithm(Brute Force)算法

  对于IT开发人员来说，字符串匹配/检索可以说是使用频率比较高的一种操作了。即使我们的400妹子，每天也会有大量的字符匹配操作，比如使用Windows自带的搜索文件功能。
  对于字符匹配的这一系列算法，我们先来介绍最简单，最易懂，但也是效率最低的一种。由于这种算法跟我们大脑的思维模式比较贴近，因此在不需要任何算法、计算机等的相关知识的情况下，也能想出来。这就是我们要介绍的Naive Algorithm（朴素算法，名字果然很朴素）或者称为Brute Force（暴力算法，我想这个名字是缘于其实现思路简单粗暴）。
  结合实际例子来讲，有一串字符aabcabcabcacabc（即我们的目标串），要让你在里面找abcabcacab（即我们的特征串），并且告诉你完全不用考虑效率，能找出来就算完成任务，目标串和特征串如下所示：

$$
\begin{split}
Text&: \qquad aabcabcabcacabc \\\\
Pattern&: \qquad abcabcacab \\\\
\end{split}
$$

  该怎么做呢？聪明的你略加思索就找到了答案，我拿着特征串，比对着目标串，从前往后，挨个挨个去比较。虽然很简单，我们还是把这个过程画一下（为了方便对比，图中绿色表示匹配成功字符，红色表示匹配失败字符。），如下所示：

  可以看出，直到第5次的时候，我们才找到了一个完全匹配。这个算法非常简单直白，就不多说，其时间复杂度（最坏情况下）为$\color{red}{O((n - m + 1)m)}$。
  关于时间复杂度，考虑到有少数同学没有学过算法分析，在这里就多说几句。时间复杂度是用来定性（注意非定量）描述算法运行时间（效率）的一个参数，常用记号$O$(ooxx)来表示，我们常用的时间复杂度有：

$$
\underbrace{O(1)}_{常数} < \underbrace{O(logN)}_{对数} < \underbrace{O(N)}_{线性} < \underbrace{O(N \cdot logN)}_{线性对数} < \underbrace{O(N^{m=2,3,…})}_{m次方} < \underbrace{O(2^N)}_{指数级} < \underbrace{O(N!)}_{阶乘}
$$

  从左往右，时间复杂度越来越高，而算法的效率越来越低。

2.4 KMP(Knuth–Morris–Pratt)算法

  KMP算法属于字符串匹配中比较经典的算法，它后面提出来的很多算法都借鉴它的一些想法。
  前面的BF算法实在是太繁琐了，每次只能跳一格来开始新一轮的匹配，每一轮的匹配还需要逐个逐个字符去比较，简直累死个人，这也是它效率极低的原因所在。那么有没有什么方法可以改进呢？几个大牛琢磨一番之后，就找到了办法，并且这个办法还比较好使。

图2-1　　Donald Ervin Knuth

图2-2　　KMP算法在目标串上的跳跃示意图

图2-3　　KMP算法在特征串上的跳跃示意图

2.4.3 Next数组之谜

  KMP算法的核心思想就是借助一个三方工具（Next数组，存放在内存中）去记录一些关键性的信息，实现匹配过程中的不断跳跃前进，从而有效的减少匹配次数。后面我们会看到还有许多算法都是这种套路，只不过玩法上有所差异。比如有个算法觉得这些关键信息放在内存中还是不够快，它干脆直接放到了寄存器里面，也是会玩。
  只要充分理解了上面的两点核心思想，KMP算法咱也就掌握了一半了。理解了KMP算法的思想之后，一些疑问也随之而来，主要体现在以下两点：

• Next数组中存放的信息为何就能精准、高效的帮我们定位到下一轮匹配的开始位置？
• Next数组的大小跟什么有关，是只需要计算一次，还是需要在匹配过程中反复计算？
• Next数组里面存放的值又是如何计算的？

  这几个问题我们一个个来解答，首先我们来看看是如何做到定位的。

2.4.3.1 定位之谜一

  如下图所示，假定我们在第$i$轮匹配时，目标串和特征串前面的$s - 1$个字符已经匹配（图中黄色虚线框内部分），而在第$s$个字符处发生了失配（图中红色不等号对应的两个方框），我们需要确定在$i + 1$轮匹配时，跳到前面已经匹配的$s - 1$个字符中的哪一个开始。

图2-4　　KMP算法在目标串上的跳跃示意图2

图2-5　　第i + 1轮匹配失败示意图

图2-6　　预匹配的情况示意图1

图2-7　　预匹配的情况示意图2

图2-8　　预匹配的情况示意图2

图2-9　　特殊情况的匹配示意图

  上图中红色双向箭头对应的是我们目标串和特征串已匹配的字符，蓝色虚线部分对应的是预匹配部分字符。当然这种情况在实际生活中出现的概率是比较小的，示例如下；

  上面说的特征串前$s - 1$个字符都要完全相同这个结论要证明是比较简单的，拿张纸随便画一画就明白了。这里我们还是给出理论证明过程，供有兴趣的参考。由于特征串与目标串已经匹配了前面$s - 1$个字符，所以有：

$$
\color{grey}{
\underbrace{p_1…p_{s-1}}_{(s - 1) - 1 + 1 = s - 1个字符} = \underbrace{t_{r-s+1}…t_{r-1}}_{(r - 1) - (r - s + 1) + 1 = s - 1个字符}
\tag{2 - 2}}
$$

  即：

$$
\color{grey}{
\begin{cases}
p_1 = t_{r - s + 1} \\\\
p_2 = t_{r - s + 2} \\\\
\cdots \cdots \\\\
p_{s - 1} = t_{r - 1} \\\\
\end{cases}
\tag{2 - 3}}
$$

  再由预匹配的条件我们有：

$$
\color{grey}{
\underbrace{p_1…p_{s-2}}_{(s - 2) - 1 + 1 = s - 2个字符} = \underbrace{t_{r-s+2}…t_{r-1}}_{(r - 1) - (r - s + 2) + 1 = s - 2个字符}
\tag{2 - 4}}
$$

  即：

$$
\color{grey}{
\begin{cases}
p_1 = t_{r - s + 2} \\\\
p_2 = t_{r - s + 3} \\\\
\cdots \qquad \cdots \\\\
p_{s - 2} = t_{r - 1} \\\\
\end{cases}
\tag{2 - 5}}
$$

  再由式（2-3）、（2-5）有：

$$
\color{grey}{
\underset{\triangle}{p_1} = t_{r - s + 1} = t_{r - s + 2} = \underset{\triangle}{p_2} = t_{r - s + 3} = \cdots = \underset{\triangle}{p_{s - 2}} = t_{r - 1} = \underset{\triangle}{p_{s - 1}}\\\}
$$

  证毕！

  我们给定的是最大前/后缀为$c = s - 2$，但实际上可以得出$c = s - 1$，与已知条件矛盾，因此这种情况不存在。实际上按照Paper中的定义，我们所谓的最大前缀必须是已匹配字符的子串。Paper中使用的是f值，因为利用f值可以非常容易的求解出Next值。结合本文，f值即为最大前/后缀大小 + 1，比如上面讲的第二种情况特征串最后一个字符处发生失配后，可以求出其最大前/后缀为$c = 1$，则该特征串字符对应的f值即为$c + 1 = 2$。

  这里要特别强调下这个f值，它是我们理解整个KMP算法的关键点，务必充分理解并牢记其定义。

  Paper中关于f值的定义原文如下：

Let f[j] be the largest i less than j such that pattern[1]…pattern[i - 1] = pattern[j - i + 1]…pattern[j- 1]

  为了平滑的与Paper的概念衔接起来，我们对一些特殊情况做些约定。对于$s \geq 3$的情况，c值可以直接用$c = s - 3$公式计算，对于$s = 1$时，规定$c = -1$（这样对应的f值即为0）。对于$s = 2$时，规定$c = 0$（这样对应的f值即为1）。
  注：Paper中是用$j$来指向失配的特征串字符，我们用的是$s$。

  于是，对给定的前后缀，其大小（长度）为$c$，我们可求出，下一轮匹配时，特征串应该沿着目标串往前移动$(s - 1) - c = s - c - 1$个字符。这是我们目标串上的跳跃值计算公式，如下所示：

图2-10　　目标串上跳跃值计算示意图

2.4.3.3 定位之谜二

  上面我们得到了目标串上的跳跃值计算公式。那么特征串上跳跃值又怎么计算公呢？
  这个问题要比目标串上的跳跃简单的多，第$i + 1$轮匹配的时候，根据预匹配的定义，特征串和目标串前面的$c$个字符已经逐一匹配了，所以我们只需要比对目标串上的$t_r$（即为上一轮失配的字符）和特征串上的第$c + 1$个字符$p_{c + 1}$即可。也就是说，在新一轮的匹配中，我们跳过特征串的前面$c$个字符，如下图所说：

图2-11　　特征串上跳跃值计算示意图

  综上所述，Next数组正是存储了这些信息，使得我们可以精准的在目标串和特征串上跳跃匹配。

2.4.3.4 Next数组大小

  解开了Next数组的定位之谜，我们来看Next数组的大小是跟什么有关，是目标串还是特征串？是只需要计算一次，还是要在匹配过程中重复计算？只有确定了这两个问题，我们才能继续讨论下一步如何计算的问题。
  我们知道Next数组保存的是当目标串和特征串发生失配的时候的跳转信息，也就是说，有多少种失配的情况，就需要保存多少条跳转记录。尽管目标串长度不定，内容也未知，但是特征串是固定和已知的。对长度为$m$的特征串，不管当前匹配到了目标串的什么位置，失配肯定是特征串的$p_0…p_m$中的某个字符与目标串不匹配，失配的情形也只有有限的$m$种，我们只需要把特征串每一个字符失配时对应的跳转信息保存起来就可以了。
  即Next数组大小只跟特征串长度有关，它的大小即为特征串长度。
  假定特征串的某一个字符在目标串不同位置上前后两次发生了失配，我们只需要考察这两种情况下的跳跃值是否有差异，就知道Next数组是否需要反复计算了，如下图所示：

图2-12　　不同位置匹配失败示意图.png

  由于两次失配时的特征串字符是相同的（已经匹配的字符数和字符内容均相同），即有$c_{s-1}^{i} = c_{s-1}^{i + k}$（因为相同特征串同一位置处其最大前缀/后缀必然是一样的），因此其在目标串上的跳跃值、在特征串上的跳跃值必然也是相同的。

  即Next数组存放的跳跃值，只需要在开始进行匹配前计算一次，只要我们要匹配的特征串不变，这些值就不会变。

2.4.3.5 F数组计算

  解开了Next数组的前两个问题，现在只剩下最后一个，即如何计算。前面我们提了下，只要求出f数组的值，就能轻松的求解出Next数组值，而f值又是跟我们的最大前/后缀紧密相关的。因此只要我们先找到最大前/后缀，就能求出相应的f值，进而求解Next值。
  最大前后缀（包括f、Next数组）的计算，用到了递归的思想：除特征串前2个字符外的每一个字符，其最大前/后缀的计算都是根据其上一个字符的最大前/后缀推算出来的。

  我们仍然以$s$指向当前要计算最大前缀的特征串字符，用$p_s$表示这个字符，再次强调，为了跟Paper结合起来，我们采用$f[t]$表示特征串索引号为t的字符的最大前/后缀长度值 + 1（也即下一个待匹配字符）。

  假定我们现在已经计算好了$p_s$的最大前缀为$c_s$（即有$f[s] = c_{s + 1} + 1$），现在要计算其下一个字符$p_{s+1}$的最大前缀$c_{s+1}$（即有$f[s+1] = c_s + 1$），如下图所示：

图2-13　　最大前后缀递归计算示意图1.png

$$
suffix’ = suffix + p_s
$$

  从图上可以看出，如果$p_s$对应的前缀的后一个字符满足$p_{c_s + 1}(pattern[f[s]]) = p_s$，那么这个字符加到之前的前缀里面去就是我们要找的前缀，即有：

$$
\begin{cases}
f[s + 1] = f[s] + 1\\\\
\\\\
preffix’ = preffix + p_{c_s + 1}
\end{cases}
$$

  此时的匹配情况如下图所示：

图2-14　　最大前后缀递归计算示意图2.png

图2-15　　最大前后缀递归计算示意图3.png

  而这个时候我们取出这个最大前缀，把这个前缀的后一个字符（即为$pattern[f[c_s+1]]$）和$p_s$比较，如果相同，则开始的$f[c_s+1]$个字符即为我们最终的$preffix’$。如果不相同，那么再以特征串索引号为$f[c_s+1]$的字符为失配字符，找到其f值，再用这个f值对应的字符和$p_s$比较。如此重复，直到找到匹配的字符或者耗尽了所有字符（不存在匹配的前缀，此时置其f值为1），如下图所示：

图2-16　　最大前后缀递归计算示意图4.png

$$
f[s + 1] = \begin{cases}
f[s] + 1, \quad if \ pattern[s] \ = \ pattern[f[s]] \\\\
\\\\
f[f[s]], \quad if \ pattern[s] \ \neq \ pattern[f[s]] \\\\
\end{cases}
\tag{2 - 6}
$$

  求最大前/后缀的算法伪代码（相较于Paper略有改动）如下：

$$
\begin{split}
& \overline{\underline{\textbf{Algorithm 1 } \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad}} \\\\
& \textbf{Input: pattern} \\\\
& \textbf{Output: f[m]} \\\\
& \textbf{function} \quad preffix\_suffix\_algorithm(pattern): \\\\
&1 \qquad m \ = \ pattern.length \\\\
&2 \qquad f[1] \ = \ 0, \quad k= \ 1\\\\
&3 \qquad \textbf{while} \ \ k \ < \ m \\\\\
&4 \qquad \qquad t:= \ f[k]\\\\
&5 \qquad \qquad \textbf{while} \ \ t \ > \ 0 \ \ \textbf{and} \ \ pattern[t] \ \neq \ pattern[k] \\\\
&6 \qquad \qquad \qquad t:=\ f[t] \\\\
&7 \qquad \qquad f[k + 1]:=\ t \ + \ 1 \\\\
&8 \qquad \qquad k:=\ k \ + \ 1 \\\\
&9 \qquad \textbf{return} \ \ f \\\\
& \underline{\textbf{end function} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad} \\\\
\end{split}
$$

  注意：前面我们已经提到了，对于特征串的第1、2个字符，其f值比较特殊，分别置为0、1。

  上式（2-6）以及其伪代码中的递归的思想其实可以用一句话来总结：既然长的后缀字符在已匹配的字符中找不到对应的前缀字符，那么我不断缩短后缀大小，就有可能在已匹配的字符中找到对应的前缀了，而缩短后缀字符最高效的办法就是利用失配（以特征串同时作为目标串和特征串）找到其对应的f值（当然你也可以一个字符一个字符的缩减，这样的话效率就会非常低了）。

  我们仍以之前所述的特征串为例，其最终的f值计算结果如下表：

  表中索引号5、6、7、8的字符其f值计算都比较简单，因为它们都满足式（2 - 6）的第一个条件，所以直接在前一个字符的f值上递增1就可以了。这里主要讲一下索引号为9的字符串，它的f值没有延续之前的递增趋势。

  如前所述，要计算$f[9] = f[8 + 1]$，先判断$pattern[8] = c$和$pattern[ \underbrace{f[8]}_{=5} ] = pattern[5] = b$是否相同，很明显两者不相同，也就是说以Pattern为目标串，以滑动后的Pattern为特征串进行匹配，在特征串索引号为5的字符$b$处发生了失配，所以$p_4…p_8 = abcac$不可能成为$p_9 = a$的最大后缀（表中蓝色字符），如下所示：

  如前所述，既然找不到长度为5的前缀，我们就利用失配（红色字符$p_5 = b$处）找到其f值从而缩减要找寻的前缀的长度。据上面的f值表可知$f[5] = 2$，这个时候后缀已经缩减到了2个字符，再次比较$pattern[8] = c$和$pattern[ f[ \underbrace{f[8]}_{=5}] ] = pattern[ \underbrace{f[5]}_{=2}] = pattern[2] = b$是否相同，如下图所示：

  对比后可知，$p_7p_8 = ac$仍然找不到对应的前缀。我们只好重复刚才的操作，得到$f[[f5]] = f[2] = 1$，这个时候后缀已经缩减到了仅仅1个字符，再次比较$pattern[8] = c$和$pattern[f[f[\underbrace{f[8]}_{=5}]] = pattern[f[\underbrace{f[5]}_{=2}]] = pattern[\underbrace{f[2]}_{=1}] = pattern[1] = a$是否相同，如下图所示：

  对比后可知，$p_8 = c$仍然找不到对应的前缀，再次重复操作，得到$f[1] = 0$，这个时候表示前面已经匹配的字符耗尽了，因此f值计算结束，并以0 + 1 = 1作为该字符的f值，即有$f[9] = 0 + 1 = 1$。

2.4.3.6 Next数组计算

  求出f值数组后，只需要做一点小小的处理就能变成我们的Next数组了。我们先给出Next数组的求解表达式，如下所示：

$$
next[s] = \begin{cases}
f[s], \quad if \ pattern[s] \ \neq \ pattern[f[s]] \\\\
\\\\
next[f[s]], \quad if \ pattern[s] \ = \ pattern[f[s]] \\\\
\end{cases}
\tag{2 - 7}
$$

  正如我们前面所述，Next数组的求解也用到了递归的思想，只是它对应的条件和f值的求解刚好相反，这点是最让人费解的。下面我们就结合例子来讲，先给出最终的f值及next值表如下：

  表中，next值与f值不同的部分均已标红。我们先来看看索引号为4的字符为什么next值变成了0，假定该特征串索引号为4这个字符处发生了失配，如下所示：

  失配后，我们取得其f值$f[4] = 1$，该值对应的特征串字符为$p_1 = a$，这个字符和我们的失配字符是相同的，即有：$p_1 = p_4 = a$，既然$p_4$在这里发生了失配，我们根据求得的f值移动特征串($s - f[s] = 4 - 1 = 3$个字符)后再次进行匹配时，也必然会发生失配，如下所示：

  既然发生了失配，必然会有跳转操作，如果我们不对这个f值进一步处理，匹配的时候就避不开这一步不必要的操作，而处理后我们可以直接跳过4个字符，然后开始下一轮的匹配。这就是为什么我们算出了f值，还要进一步算next值的原因。如果你事先了解一些NFA和DFA的知识的话，f值的作用就有点类似我们的NFA，而next值则是DFA，想进一步了解可参考2.4.3.7节所述。

  那这里跳过4个字符是怎么得出来的呢？首先特征串第一个字符处发生失配后，其f值为$f[1] = 0$，因此我们要跳过$s - f[s] = 1 - 0 = 1$个字符，再开始下一轮新的匹配。再结合之前跳过的3个字符，一共就是4个！

  结合式（2-7）的第二条来看，$next[4] = next[f[4]] = next[1] = 0$。索引号7、9的字符其next值为0的原因也是一样的，大家可以自己推导一下。

  我们再来看索引号为8的特征串字符$p_8 = b$，假定在该字符处发生了失配，如下所示：

  失配后，我们取得其对应的f值$f[8] = 5$，该值对应的特征串字符为$pattern[f[8]] = pattern[5] = b$，这个字符和我们的失配字符是不相同的，即有：$p_5 \neq p_8$，既然这个字符与发生失配的字符不相同，那么跳转后下一轮匹配时，上一轮失配的地方就有可能不会再失配，因此我们就使用这个值作为next值，这就是式（2-7）的第一个条件的来源！

  当然我们举得这个例子里面，跳转后在原来发生失配的地方还会再一次发生失配，如下所示：

  其实这里还有一个问题，可能会让人有些困惑，既然跳转后的特征串我们知道了是$b$，发生失配的目标串字符是$a$，两者不相同，再次发生了失配，为什么不进一步处理以获得最终的next值呢？

  原因就在于，我们要匹配的目标串是动态变化并且是不可预知的，这个例子发生失配后经过一次跳转再次发生了失配，但是在目标串的其它地方，跳转后可能就匹配上了！举个例子来讲，比如特征串第八个字符在目标串上某处再次发生失配，如下所示：

  如上表所示，上一轮失配的字符，在下一轮匹配时却匹配上了。而后面还没有匹配的目标串中，可能还存在大量这样的例子，每一次你都无法预料跳转后是否能匹配上，还得老老实实做一次匹配。

  至此，式（2-7）的两个条件我们就解答完了，这里我们再对比下next数组值和f数组值的异同：

• 两者均可在失配发生后，计算移动的字符数；
• f数组值没有对失配后的跳转做进一步判断，Next数组值对能处理的都做了处理，计算出其最高效的跳转值；
• 特征串第一个字符失配后，其f值和Next值均为0；
• 特征串除第一个字符外的所有字符发生失配后，如果前面找不到有效的前缀，f值为1，而next值为0；

  在实际实现上，我们完全可以把next值和f值的求解融合在一起，而完全不需要单独存储f值，也不需要等所有f值求解完了之后再来转换成next值。算法（相较于Paper略有改动）伪代码如下：

$$
\begin{split}
& \overline{\underline{\textbf{Algorithm 2 } \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad}} \\\\
& \textbf{Input: pattern} \\\\
& \textbf{Output: next[m]} \\\\
& \textbf{function} \quad next\_precompile(pattern): \\\\
&1 \qquad m \ = \ pattern.length \\\\
&2 \qquad next[1] \ = \ 0 , \quad k = 1 , \quad t= \ 0\\\\
&3 \qquad \textbf{while} \ \ k \ < \ m \\\\\
&4 \qquad \qquad \textbf{while} \ \ t \ > \ 0 \ \ \textbf{and} \ \ pattern[t] \ \neq \ pattern[k] \\\\
&5 \qquad \qquad \qquad t:=\ next[t] \\\\
&6 \qquad \qquad t:=\ t \ + \ 1 , \quad k:=\ k \ + \ 1 \\\\
&7 \qquad \qquad \textbf{if} \ \ pattern[t] \ = \ pattern[k] \\\\
&8 \qquad \qquad \qquad next[k]:= \ next[t] \\\\
&9 \qquad \qquad \textbf{else} \\\\
1&0 \qquad \qquad \qquad \ next[k]:= \ t \\\\
1&1 \qquad \textbf{return} \ \ next \\\\
& \underline{\textbf{end function} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad} \\\\
\end{split}
$$

  分析可知，计算f数组以及Next数组的时间复杂度均为$O(m)$，这里不做展开，在Paper第6页有详细的分析说明，感兴趣请自行参阅。

2.4.3.7 NFA和DFA的类比说明

  前面说到了f值类似我们的NFA，next值类似我们的DFA，这里举个例子来予以说明，方便没有相关知识的同学去理解f值和next值的区别。仍以前面的例子来说，我们有f值及next值如下表：

  我们来看索引号为4的特征串，假设在这里发生了失配，按照上述f值的移动(4-1=3)、next值移动(4 - 0 = 4)特征串后如下所示：

  可以看出，失配后，根据f值我们只能往前移动$4 - f[4] = 4 - 1 = 3$个字符，然后比对特征串第1个字符$pattern[f[4]] = pattern[1] = a$和目标串第4个字符$b$，发现再次失配，然后特征串再往前挪动一格，到达我们按照next值所移动到的位置。很明显这一步是完全没有必要的，我们可以直接跳到目标串索引号为5的字符$a$处开始。

  上一轮匹配时特征串字符为$a$，发生了失配，根据f值跳转后，我们要匹配的第一个特征串字符仍然是$a$，这就必然会导致再次失配。但由于f值仅仅存储的是失配处字符前面的最大前/后缀，没有关于前/后缀的下一个字符的信息，所以使用f值是无法避免大量重复匹配的。

  而next值保存的是，让你在不漏匹配的情况下，最大移动的字符数。

2.4.4 完整KMP代码

  在本节的最后，我们给出完整的KMP算法伪代码，如下所示：

$$
\begin{split}
& \overline{\underline{\textbf{Algorithm 3 KMP} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad}} \\\\
& \textbf{Input: text, pattern} \\\\
& \textbf{Output: index(1st match) or -1(no match)} \\\\
& \textbf{function} \quad kmp\_algorithm(text, \ pattern): \\\\
&1 \qquad m \ = \ pattern.length, \quad s \ = \ 1(ptr \ of \ pattern)\\\\
&2 \qquad n \ = \ text.length, \quad r \ = \ 1(ptr \ of \ text)\\\\
&3 \qquad next \ = \ next\_precompile(pattern)\\\\
&4 \qquad \textbf{while} \ \ s \leq \ m \ \ \textbf{and} \ \ r \leq n\\\\\
&5 \qquad \qquad \textbf{while} \ \ s \ > \ 0 \ \ \textbf{and} \ \ pattern[s] \ \neq \ text[r] \\\\
&6 \qquad \qquad \qquad s:=\ next[s] \\\\
&7 \qquad \qquad s:=\ s \ + \ 1 , \quad r:=\ r \ + \ 1 \\\\\
&8 \qquad \textbf{if} \ \ s \ > \ m\\\\
&9 \qquad \qquad \textbf{return} \ \ r - 1\\\\
1&0 \qquad \textbf{else}\\\\
1&1 \qquad \qquad \textbf{return} \ \ -1\\\\
& \textbf{end function} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\\\
\\\\
& \textbf{function} \quad next\_precompile(pattern): \\\\
1&2 \qquad m \ = \ pattern.length \\\\
1&3 \qquad next[1] \ = \ 0 , \quad k = 1 , \quad t= \ 0\\\\
1&4 \qquad \textbf{while} \ \ k \ < \ m \\\\\
1&5 \qquad \qquad \textbf{while} \ \ t \ > \ 0 \ \ \textbf{and} \ \ pattern[t] \ \neq \ pattern[k] \\\\
1&6 \qquad \qquad \qquad t:=\ next[t] \\\\
1&7 \qquad \qquad t:=\ t \ + \ 1 , \quad k:=\ k \ + \ 1 \\\\
1&8 \qquad \qquad \textbf{if} \ \ pattern[t] \ = \ pattern[k] \\\\
1&9 \qquad \qquad \qquad next[k]:= \ next[t] \\\\
2&0 \qquad \qquad \textbf{else} \\\\
2&1 \qquad \qquad \qquad \ next[k]:= \ t \\\\
2&2 \qquad \textbf{return} \ \ next \\\\
& \underline{\textbf{end function} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad} \\\\
\end{split}
$$

  KMP算法总的时间复杂度（包括预计算Next数组）为$O(m + n)$，如果只考虑匹配/搜索部分的话，为$O(n)$。这些无论是《算法导论》还是原始Paper中都有详细的分析，限于篇幅，这里就不再展开。

2.5 KMP优化和扩展

  KMP算法的实现不可谓不精妙，尤其是前/后缀的引进，犹如神来之笔，然而即使这样，上面的算法匹配性能也还有许多可优化之处。
  此外，上面的代码检测到第一个特征串之后就停止了，也即只能检测出目标串中最左边的特征串，稍做处理之后，KMP可以把整个目标串中的特征串都检索出来。

2.5.1 性能优化

  KMP算法在其Paper中提到，在实际的应用场景中，上述没有优化过的KMP算法实际的表现性能可能还不如暴力匹配算法，原话是这么说的：

In fact, the algorithm as presented above would probably not be competitive with the naive algorithm on realistic data, even though the naive algorithm has a worst-case time of order m times n instead of m plus n, because the chance of this worst case is rather slim.

  作者的意思很明确，虽然KMP理论上的时间复杂度为线性$O(m + n)$，而BF算法最坏情况下为$O(m \cdot n)$，但毕竟这种情况在实际应用中是极难遇到的。针对上述算法存在的问题，作者从以下几个方面入手，分别介绍了问题的根源，以及对应的解决办法。

2.5.1.1 Large alphabet of characters

  当我们字符串中的字母很多的时候，我们很难得到一次部分匹配(partial match)，几乎都是在特征串第一个字符处就发生了失配，比如有目标串$bc…xyz$，特征串$ac…$，特征串每次在首字符就发生失配，然后查Next数组有$next[1] = 0$，于是用这个值更新特征串指针$s:= next[s]$，然后判断这个指针是否越界$s \leq m$。我们每次都只能往右移动$1 - 0 = 1$个字符，然后去进行各种各样的判断，导致效率异常底下，这种情况下KMP的效率与我们的BF算法其实是一样的。

  解决的办法是，将$s = 1$这种情况作为特殊例子来处理。具体做法是，当在特征串的首字符处失配时，不去查Next表，也不用去更新$s$以及判断其是否越界，直接将目标串指针$r$自增1再判断（即指向下一个目标串字符）即可，部分伪代码如下：

$$
\begin{split}
& \underline{ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad} \\\\
&1 \qquad \textbf{while} \ \ s = 1 \ \ \textbf{and}\ \ text[r] \neq \ pattern[1] \\\\
&2 \qquad \qquad r:= \ r \ + \ 1 \\\\
&3 \qquad \qquad \textbf{if} \ \ r > n \\\\
&4 \qquad \qquad \qquad break \\\\
& \underline{ \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad} \\\\
\end{split}
$$

2.5.1.2 全匹配检测

  每一轮新的匹配开始前，我们都要对目标串以及特征串的指针做越界检测（即检测$s \leq m, \ r \leq n$是否满足），以便判断是否已经找到了满足要求的特征串（全匹配），从而浪费了大量不必要的时间。

  处理办法是特征串的最后增加一个永远不会被匹配的字符，比如“@”，以此判断指针已经到达了字符串的尾部边界处，同时置该字符的next值为-1，即$next[m + 1] = -1$。于是就可以把对$s > 0$的判断放在执行不那么频繁的代码段中。

  当然，我们还可以对目标串我们也采用类似的方法，比如在其尾部添加一个字符“$\perp$”作为边界标志，同时添加特征串首字符$pattern[1]$从而避免频繁的去做越界检测，即$text[n + 1] = \perp, \ text[n+2] = pattern[1]$。

2.5.1.3 预编译机器码

  上面给出的例子是一种通用的解决方案，但是在某些应用场景下，效率还不是最高的。比如在文本编辑器中使用查找功能时，我们输入的特征串都是比较短的，因此我们预先把特征串（隐式的包含了Next数组）编译成机器码，就可以大大的提高效率。

  比如可以编译成如下的机器码：

1
2
3
4
5
6

L0:    k:= k + 1
L1:    if text[k] $neq$ b then go to L0:
           k:= k + 1
       if k > 0 then go to L3:
            ··· ···
L3:    ··· ···

2.5.2 扩展

  KMP算法没有扩展前只能匹配目标串最左边的第一个特征串，并且只是单模匹配。要实现更强大的功能就需要做一些改进。

2.5.2.1 全部检索

  要想把所有特征串都检索出来，作者提到了一种方法，那就是新增一个resume变量同时结合上面提到的在特征串尾部添加越界标识字符的方法。添加越界字符后，计算这个越界字符的Next值$next[m + 1]$，然后将这个值赋给resume，最后再将$next[m + 1]$置为-1。当我们检测到一次完全的匹配之后，使用resume的值更新特征串指针$s$的值，从而恢复执行。

  但需要注意的是resume的值一定不能为0（这样匹配算法中内存循环的$s > 0$就无法满足）。

2.5.2.3 多模匹配

  KMP要实现多模匹配，需要做大量的工作，都可以再单独写一篇分析的文章了，感兴趣可自行参考Paper，在此不赘述。

三、结语

  能够坚持看到这里，我相信你一定会有所收获。其实KMP算法是众多匹配算法中最难理解的之一，我没在开篇的时候提出来，就是不希望给读者带来太大压力。要搞懂KMP的精髓，真的是需要花大量时间反复的去揣摩、推导。本文为了兼顾一些没有相关背景的同事，所以有点偏长，疏漏也在所难免，希望及时指正。

  如果你没看懂，不要怀疑自己，一定是我没有讲清楚，请务必在评论中指出（目前查看、回复评论均需要代理）。

  我们一直坚信，授人以鱼远不如授人渔。

  参考资料如下：

1. 从头到尾彻底理解KMP（2014年8月22日版）;
2. 字符串匹配的KMP算法;
3. KMP 算法 —— 字符串匹配算法;
4. 柔性字符串匹配;
5. 算法导论;