本文共 2355 字，大约阅读时间需要 7 分钟。
这两天在看字符串匹配算法，第一次看到KMP算法的时候觉得很难。于是上网搜分析，网上讲KMP的算法很多，只是好像很多都讲的云里雾里的，不甚清晰。后来想想还是找教材看看，第一回看的是《算法》第四版，其实没看懂；于是再找来CLRS看，恍然大悟，果然还是CLRS大法好。本文主要是梳理一下整个思路，尽自己所能讲得尽量清晰易懂。
首先先从什么是字符串匹配开始：字符串匹配就是给定一个字符串S，然后在另一个字符串T中找出S。具体应用上可以是找出S在T中出现了多少次，S在T中出现的位置等等，也就是很多文本编辑器的ctrl+f的功能了。
显然这里存在一个大家都想得到的原始暴力型的算法，基本思想就是：把T中的每个字母T[1......m-p]和S[1]中的第一个字母比较，假设当前比较到T中的第j个字母，且T[j]==S[1]，则继续依次比较T[j+i]和S[1+i]，i=1....p-1.其中p为S的长度。直到i==p-1或者T[j+i]!=S[1+i]，则终止当前以j为起点的比较，并令j=j+1继续下一轮的比较；如果一开始T[j]!=S[1]则直接j=j+1，进入下一轮比较。代码很简单，如下：
int search(string s,string t){ int slen = s.length(); int tlen = t.length(); for(int j=0;j 假设S的长度为M，T的长度为N，则此算法的时间复杂度 为O(M*N)。 而本文的重点接下来介绍的KMP算法可以使时间复杂度为O(N)。
KMP算法
kmp算法之所以能够降低时间复杂度，是因为在每次的匹配过程中，它都用到了上次匹配时所获得的信息。
比如现在假设长的字符串为T，短的字符串为S
在当前的匹配过程中，当匹配到红色的地方时，两个字符串对应的字符不一样，即不能再继续进行匹配了；虽然这个匹配是失败的，但是我们可以从中得到一些有用的信息：假设红色区域在S中的下标为i，在T中的下标为j，则显然S[1...i-1]和T[j-i+1....j-1]是匹配的。即红色区域之前的两个字符串中的对应字符是一样的。现在问题是怎么利用这个信息呢？回忆一下之前的暴力算法。在暴力算法中，当当前匹配失败时，将重置S和T的下标。其中i继续从0开始，而j=j-i+1+1。
KMP的想法是在匹配过程中保持j不变，而减小i，但i很多时候不必要从1开始。
当匹配失败时，我们可以想象一下，如上图，固定字符串T，将S从左向右滑动，直到上图中两条直线区域内的两个字符串的重叠部分相互匹配，或者直线区域内S为空时则停止滑动。对于第一种情况，假设和T中红色部分匹配的S的下标为k，则令i = k+1，并j=j+1就可以继续匹配下去，而不需要再比较k之前的字符。通过以上的分析可以发现，k满足下面的条件
S[1....k-1] = S[p.....i-1]，其中 i - 1 - p = k - 1 - 1
而显然对于以上算法，如果k的值越大，匹配所需的比较就越少，因此k应该是"S的最长的前缀子串，同时该子串也是字符串S[1...i-1]的后缀子串"的长度。因此假如有一个数组a[1.....S.length()]可以保存，S中每个下标下对应的最大K值，则在匹配时，如果匹配失败，就可以直接通过使用数组找到k，使i=k+1继续匹配，因此在得到数组a的情况下，我们可以实现KMPsearch函数如下：
int KMPsearch(string s,string t){ int slen = s.length(); int tlen = t.length(); //int *a = new int[slen]; vector a(slen,0); get_arr(s,a); int j = -1; for(int i = 0 ; i < tlen ; ++i) { while(j>=0 && s[j+1]!=t[i])j = a[j]; if(s[j+1] == t[i])j++; if(j==slen-1)return i-j; } return -1;} 很简单的一段代码。所以现在问题的关键在于找到实现get_arr函数，亦即找到S对应的数组。其实这本身也是KMP算法的关键。 其实这个问题也不难，可以用归纳法来思考。
首先假设当前已经找到a[1...k]，则怎么找a[k+1]呢？根据定义，假设 a[k] = q，则S[1.....q] = S[p....k]，其中k-p=q-1；所以a[k+1]最大应该等于q+1，但如果S[K+1]!=S[q+1]，则a[k+1]<q+1;但我们可以知道，若a[k+1]=r，则要么存在u，使得S[1...u]=S[h....r]，其中r-h=u-1，此时可以知道S[1....u-1]也是原来的S[p....k]的后缀表达式；要么a[k+1]=0，即找不到满足等式条件的r。
由以上描述可以知道，我们可以遍历当前的所有 "既是S[p....k]的后缀表达式，又是S的前缀表达式" 的子串,假设为S[1.....f]，然后找出满足S[f+1]=S[q+1]的最大f，此时可得到 a[k+1]=f。
根据以上描述代码如下：
void get_arr(string s,vector &a){ a[0]=-1; int p=0; int k=-1; int len = s.length(); for(p=1;p =0 && s[k+1]!=s[p])k = a[k]; if(s[k+1]==s[p])k = k+1; a[p] = k; }}