前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

---

这一篇，我们来讨论一个问题——字符串的模式匹配问题，同时介绍一种经典算法KMP算法。

说起KMP算法，博主还真是有不少话想说。

咱就先不说博主这是第五次才把他学会，就这个算法名字而言，它就经常被戏称为 看毛片 算法。但其实他是三位发明该算法的大佬（Knuth，Morris，Pratt）名字的简写。

这个算法简洁、高效、且优美。通过定义一个巧妙地函数，完美的解决了一个字符串的基础难题：模式匹配。那么就让我们先从这个问题入手吧。

模式匹配问题

模式匹配问题很好理解。

给定两个字符串：模式串P和文本串s，求出p在s中出现的位置

举个例子：

$$\begin{gathered} 给定文本串S:qwerabcdabcrewq \\ 给定模式串P:abc \\ 问P在S中所有的出现位置 \end{gathered}$$

对于这个例子，一眼看去就能找到所有答案;

两个答案分别是4和8；

但是计算机可没有“一眼看去”的技能，他只能通过算法来得到这个问题的答案。

朴素的模式匹配算法

用算法来实现模式匹配的任务，一个最朴素的想法，是将模式串逐位的放在文本串上进行验证。

也就是这样：

这个算法实现起来不难，两重循环，分别固定模式串起始位置，验证匹配。

//C void match(char * p,char * s){ int lp = strlen(p); int ls = strlen(s); for(int i = 0;i < ls - lp + 1;i++){ for(int j = 0;j < lp;j++){ if(s[i + j] != p[j]) break; if(j == lp - 1) printf("%d ",i); } } }

运行: 答案没有问题。

但是朴素算法的弊端就在于其复杂度太高，从刚才的算法实现中不难看出其复杂度为 O(nm) 其中n为模式串的长度，m为文本串的长度。

这个复杂度伴随着文本串和模式串的增长而成平方增加。这种复杂度是不能接受的！！！

究其原因就在于它在执行过程中进行了太多次没有意义的跳转和比较，有些位置的比较实际上是不需要的。

比如，对于如下匹配：

$文本串：abababaac$ $模式串：abaa$

当第四个字符失配时，按照朴素算法的思路，应该放弃将模式串与文本串第一位对应，转为对应第二位再进行判定，但实际上，模式串并不需要在第二位上面继续比较，而可以直接去第三位的位置进行这个过程，因为那里是以a开头的。

要改进这个思路，就需要让模式串失配时，在保证算法正确性的基础上，让模式串尽可能多的向后移动，进而提高效率。这就需要利用已有的信息或者模式串本身的特点。

为了解决这个问题，下面我们需要引入一个函数，它能体现字符串本身的特性，并且能够很好地指导该字符串在匹配过程中失配时的行为。

KMP算法

对朴素算法改进的讨论

（该过程是博主本人对引出算法的过渡讨论，不影响后续对失败函数的叙述，可以选择观看。当然，同博主一起讨论这部分内容可能会帮助理解算法）

遵从上面的指导思想，我们想要在模式串失配时可以尽可能快速的移动到下一个合适的地方进行后续匹配。

在刚才的例子中，我们找到了文本串中下一个同模式串开头的相同的地方。但不能总是使用这个策略，因为这个策略仍旧要比较所有的后续字符，本质上与普速算法没有区别。

不妨设： $模式串P:p_0{p}_1{p}_2...p_m$ $文本串S:s_0{s}_1{s}_2....s_n$

进一步想，如果可以，直接跳到下一个与头两个元素相同的位置，将会比跳到下一个与首元素相同的位置更优，会再少比较一次。

$...s_k{s}_{k+1}{s}_{k+2}...s_n$ $p_0{p}_1...p_m$ $(s_k=p_0,s_{k+1}=p_1)$

那么三个呢，四个呢？肯定更优。甚至于如果直接能匹配m个，那任务就完成了2333。再仔细想，这样的想法本质上是希望模式串能够跳转到匹配其最长前缀的地方。

虽然想法是好的，但是问题就在于无从得到在文本串中出现前缀的所有地方，一来模式串中的前缀有m个，二来前缀也是字符串，匹配前缀本身又是个规模更小的模式串匹配问题，这导致问题不但没有简单，反而更复杂了。

所以对于找到下一个匹配某个前缀的位置的问题，我们需要换个思路。

注意到在朴素算法匹配的过程中，未被扫描到的文本串内容与模式串的匹配关系是未知的，而被匹配过的内容却是已知的。

举个例子：

在当前匹配中，前三个位置是匹配成功的，在模式串第四位失配了。此时在文本串中4之前的位置匹配结束，我们不关心，7之后的内容未经匹配，匹配结果未知。但是在4到6之间是已经同模式串匹配过的地方，匹配关系是明确的。

如果能在已经知道匹配关系的区间，找到下一个模式串的前缀，并且以失配的前一位为结尾的位置，就可以直接跳过去了。

用一张图表示：

稍加思索不难发现一个问题，这个位置只和模式串的字符排列特点决定的，与文本串无关。换句话说，是模式串本身的某个前缀中，其某个真前缀与对应长度的后缀内容相同。

即： $对于模式串P:p_0{p}_1{p}_2...p_m$ $任取0<j\le m,可能存在0\le k<j，满足$ $p_0{p}_1..p_k=p_{j-k}{p}_{j-k+1}..p_j$

$例如：abcabd中$ $$\begin{gathered} 取j=4,可得abcab \\ 则有k=1或2 \end{gathered}$$ $满足a=a或ab=ab$

如果知道了每个长度k对应的j，那么每次匹配失败时的跳转问题就能够很好解决了。当然需要注意的是，不是每个前缀都有前后缀相同的情况，例如abc就没有这样的j。

到这里，为方便进一步讨论，是时候对这些概念下个定义了。

失败函数定义

我们定义失败函数f(j)为字符串的前缀$p_0{p}_1...p_j$中，最长的相等真前缀与真后缀的长度。对于不存在这样k的情况，我们约定其函数值为-1.

即： $$f(j)=\{\begin{array}{cc}k& k为满足0⩽k<j,且p_0{p}_1...p_k=p_{j-k}{p}_{j-k+1}...p_j的最大整数\\ & -1其他情况\end{array}$$

KMP算法进行模式匹配

有了对失败函数的定义，下面就可以尝试使用失败函数来进行模式匹配了。

我们设匹配过程中，对模式串的指针为j，文本串的指针为i每次匹配时：

若新位置的字符($s_i,p_j$)能够匹配，那么就将模式串和文本串指针向后移动(i++,j++)，重复过程，匹配下一位。 若模式串的指针指向末尾，则表明完成了一次匹配，找到了文本串中出现的一个模式串，输出出现位置(i - j)，再将模式串指针置于其失败函数处f(j - 1) + 1(加1是为了指向待匹配的新的字符) 若新位置的字符失配($s_i,p_j$) 当该字符不是模式串首位时，将模式串的指针向前移动到上一位的失败函数处f(j - 1)+1 否则将文本串匹配位置向后移动一位(i++) 若文本串的指针指向末尾，整个匹配过程结束。

使用C语言实现上述过程:

//C void kmp(char *p,char *s,int *f){ int lp = strlen(p); int ls = strlen(s); int idxP = 0; int idxS = 0; while(idxS < ls){ if(s[idxS] == p[idxP]){ idxS++; idxP++; if(idxP == lp){ printf("%d ",idxS - idxP); idxP = f[idxP - 1] + 1; } }else{ if(idxP == 0){ idxS++; }else{ idxP = f[idxP - 1] + 1; } } } }

运行一下：

可以证明的是，这个算法的复杂度为$O(n+m)$。

一下就从乘积复杂度降至线性复杂度，这个复杂度是我们可以接受的。

失败函数的实现

不难看出，要实现kmp算法，重中之重就在于能求解出模式串的失败函数。

下面就来屡一下如何求解失败函数。

求解失败函数，我们需要使用到数学归纳法的思想，也就是如何利用之前已经求出的结果通过递推关系来得到后面的结果。

假设当前要求解$f(i),i>0$，$f(k),0\le k<i$已知。

其实不难发现，相邻的失败函数值至多增加1，相当于前后缀都向后拼接一位， 如$abcab$中有$ab=ab$,拼上一位$c$后有$abc=abc$。 于是$f(i)$一定不会超过$f(i-1)+1$，那么就从这一步判起。

若$s_{f(i-1)+1}=s_i$，也就是如下情况： 那么$f(i)=f(i-1)+1$。那如果$s_{f(i-1)+1}\ne s_i$呢？也就是如下情况： 当失配时，可使当前的前缀变短，尝试找到仅次于$f(i)$的第二长度$j<f(i)$，使得$j$满足 $$s_0{s}_1...s_j=s_{i-j}{s}_{i-j+1}...s_i$$ 如果再次失配，那就进而寻找更小的$j$直到最后配对成功或者完全失配。 为了寻找这个$j$，让我们来回顾一下失败函数的非-1时的定义，即$s_0{s}_1...s_i$中长度为$f(i)$的前后缀是完全相等的，那么可以得到： $$s_0{s}_1...s_{f(i)}=s_{i-f(i)}{s}_{i-f(i)+1}..s_i$$ 形象点说，就是上图中两段红色的子串完全相等。 那么后缀中取到的子串必然能够在前缀中取到。那么长度为$j$的后缀既是长度为$i$的子串的后缀，也是长度为$f(i)$子串的后缀，即对于$j$有： $$s_0{s}_1...s_j=s_{f(i)-j}{s}_{f(i)-j+1}..s_{f(i)}$$ 形象点表述为： 只要理解到这里，答案就呼之欲出了。这个$j$其实就是$f(f(i))$!!

因此根据上面的分析，终于可以得到迭代递推的算法：

在匹配的开始可令$j=f(i)$。特别的，令$f(0)=-1$失配时令$j=f(j)$，继续这个过程配对成功，即$s_{j+1}=s_i$时，即可得到答案$f(i)=j+1$若全程匹配失败，即$j$迭代至$-1$时，失败函数取其他情况，即$f(i)=-1$

上述过程使用代码实现也是惊人的简洁:

//C int * getF(char * p){ int len = strlen(p); int * f = (int*)malloc(sizeof(int) * len); for(int i = 1,j;i < len;i++){ j = f[i - 1]; while(j >= 0 && p[j + 1] != p[i]) j = f[j]; if(p[j + 1] == p[i]) j++; f[i] = j; } return f; } public int[] getF(String s){ char[] str = s.toCharArray(); int[] f = new int[str.length]; f[0] = -1; for(int i = 1,j;i < len;i++){ j = f[i - 1]; while(j >= 0 && str[j + 1] != str[i]) j = f[j]; if(str[j + 1] == str[i]) j++; f[i] = j; } return f; }

该算法的操作次数为$O(n)$

模式匹配的另一种解法

模式匹配当然不仅只有上面一种求法，失败函数也不会只有一种用法。

我们将模式串$P$和文本串$S$ 按照如下方式拼接： $$\begin{gathered} p_0{p}_1...p_m\ast s_0{s}_1...s_n \\ 其{中}^{\prime }{\ast }^{\prime }为分割字符，该字符不能出现在P和S中 \end{gathered}$$ 例如： $$\begin{gathered} 模式串：abc \\ 文本串：qwerababcga \\ 拼接串：abc\#qwerababcga \end{gathered}$$ 接着对拼接串求解失败函数。

由于我们添加了分割字符，因此所有的失败函数值都不会超过$|P|$，从分隔符后面开始，其失败函数$f(i),|P|\le i\le |P|+|S|$的意义又可以被描述为：$文本串中以s_{i-|p|}为结尾的字符串能匹配上模板串中的位数$ 即下图中两段相等：

$$\underset{f(i)}{p_0{p}_1..}..p_m\#s_0{s}_1..\underset{f(i)}{..s_{i-m}}...$$

所以，如果出现$f(i)=|P|-1$： $$\underset{f(i)}{p_0{p}_1...p_m}\#s_0{s}_1..\underset{f(i)}{..s_{i-m}}...$$

即文本串中出现了一个完成的模式串，也就找到了一个匹配。

算法复杂度来源于计算失败函数和遍历寻找答案，最终复杂度仍然为$O(n+m)$

示例代码（求模式串在文本串中出现的所有位置）：

//C #include<stdio.h> #include<string.h> #include<malloc.h> int * getFailed(char * s){ int l = strlen(s); int * f = (int*)malloc(sizeof(int) * l); f[0] = -1; for(int i = 1,j;i < l;i++){ j = f[i- 1]; while(j >= 0 && s[i] != s[j + 1]) j = f[j]; if(s[i] == s[j + 1]) j++; f[i] = j; } return f; } int main(){ char a[200050]; char b[200050]; //a是文本串，b是模式串 scanf("%s%s",a,b); int la = strlen(a); int lb = strlen(b); int * f = getFailed(strcat(strcat(b,"$"),a)); for(int i = 0;i < lb;i++){ printf("%d ",f[i]); } printf("\n"); for(int i = lb - 1;i < la + lb + 1;i++){ if(f[i] == lb - 1){ printf("%d",i - lb * 2); break; } if(i == la + lb){ printf("-1"); } } free(f); }

失败函数与前缀函数

有一些地方在描述kmp算法时引入的是前缀函数，比如Oi Wiki。

那里给他的定义为： 其与失败函数的定义存在出入的地方：

当存在相同的真前缀与真后缀时，前缀函数函数值含义描述为真前缀和真后缀的长度，而非失败函数描述的最后元素的下标，由于下标是从0开始计算的，前缀函数值比失败函数值多1。

对于没有相同的真前缀与真后缀的情况，使用前缀函数的定义其相同长度为刚好为0，而失败函数给其特殊定义为-1，同样是前缀函数比失败函数多1

所以，综上所述，失败函数$f(i)$和前缀函数$\pi (i)$满足关系：$f(i)=\pi (i)-1$，二者可以相互转化，本质上描述的性质相同。

最后，KMP算法的精髓就在于失败函数的定义及求解。对于这样一个精致的描述字符串特殊性质的函数，其妙用一定不止匹配字符串一处，它还可以用以处理更多有关字符串的问题，大家可以在Oi Wiki上找到这些用法。

---

往期博客

【数据结构基础】数据结构基础概念【数据结构基础】线性数据结构——线性表概念 及 数组的封装【数据结构基础】线性数据结构——三种链表的总结及封装【数据结构基础】线性数据结构——栈和队列的总结及封装(C和java)

---

参考资料：

《数据结构》（刘大有，杨博等编著）《算法导论》（托马斯·科尔曼等编著）《图解数据结构——使用Java》（胡昭民著）OI WiKi