夕拾算法进阶篇：22)KMP算法详解

之前在数据结构书上面看过KMP算法的介绍，但是一直没有弄懂。发现胡凡的《算法笔记》对该算法的描述非常透彻，因此记录下(ps:下面的图片来自于该书)

next数组

在正式进入KMP算法之前，先来学习一个重要的数组。假设有一个字符串s(下标从0开始)，那么它以i结尾的子串就是s[0..i]，对于该子串来说，长度为k+1的前缀和后缀分别是s[0..k]和s[i-k..i]，现在定义一个数组next(请先不要在意名字)，其中next [i]表示使子串s[0..i]的前缀s[0..k]等于后缀s[i-k...i]的最大k(注意前缀和后缀可以重叠，但不能是s[0..i]本身)；如果找不到相同的前后缀，就令next[i]=-1。换句话说，next[i]就是所求最长相等前后缀中前缀的最后一位的下标 (ps:这句话非常重要！)

以字符串s="ababaab"为例，next数组的计算过程如下所示，图中给出了上框和下框是等价的表示，其中上框的前后缀用下划线表示出了，而下框把后缀和前缀用2行来分开表示。建议先看上框再看下框，会有不一样的体验喔。

(1) i=0，子串s[0..i]为“a”，前后缀不能是子串本身，因此令next[0]=-1

(2)i=1，子串s[0..i]为“ab”，由于找不到相等的前后缀，因此令next[0]=-1

(3)i=2，子串s[0..i]为“aba”，能使前后缀相等的最大的k等于0，此时前缀s[0..k]="a"，后缀s[i-k,i]="a"，而当k=1时，前缀s[0..k]="ab"，后缀s[i-k,i]="ba"，它们不相等，因此next[2]=0

(4)i=3，子串s[0..i]为“abab”，能使前后缀相等的最大的k等于1，此时前缀s[0..k]="ab"，后缀s[i-k,i]="ab"，而当k=2时，前缀s[0..k]="aba"，后缀s[i-k,i]="bab"，它们不相等，因此next[3]=1

(5)i=4，子串s[0..i]为“ababa”，能使前后缀相等的最大的k等于2，此时前缀s[0..k]="aba"，后缀s[i-k,i]="aba"，而当k=3时，前缀s[0..k]="abab"，后缀s[i-k,i]="baba"，它们不相等，因此next[4]=2。

(6)i=5，子串s[0..i]为“ababaa”，能使前后缀相等的最大的k等于0，此时前缀s[0..k]="a"，后缀s[i-k,i]="a"，而当k=1时，前缀s[0..k]="ab"，后缀s[i-k,i]="aa"，它们不相等，因此next[5]=0。

(7)i=6，子串s[0..i]为“ababaab”，能使前后缀相等的最大的k等于1，此时前缀s[0..k]="ab"，后缀s[i-k,i]="ab"，而当k=2时，前缀s[0..k]="aba"，后缀s[i-k,i]="aab"，它们不相等，因此next[6]=1。

再次强调：next[i]就是子串s[0..i]的最长相等前后缀中前缀的最后一位的下标。

现在的问题是如何来求解next数组？假设已经求得了next[0]=-1、next[1]=-1、next[2]=0、next[3]=1，现在来求解next[4]。参看下面的图，next[3]=1时，最长相等的前后缀为“ab”，之后再计算next[4]时，由于s[4]==s[next[3]+1]，因此可以把最长相等前后缀扩展为“aba”，而此时next[4]=next[3]+1=2，并让j指向next[4] (j的作用在代码中体现)。

接着在求next[5]，但是由于s[5]!=s[next[4]+1]，因此无法扩展最长相等前后缀，即无法通next[4]+1的方法获得next[5]。这个时候怎么办呢？既然前后缀没有办法达到那么长，那么不妨缩短一点！此时希望找到一个j,使得s[5]=s[j+1]成立并且s[0..j](下图中的波浪线～)是s[0..2]=“aba”的后缀(s[0..j]显然是s[0..2]的前缀)。同时为了让找的的相等前后缀尽可能长，找到的j应该尽可能大。

是否想到什么了？实际上要求图中波浪线的部分(即s[0..j])既是s[0..2]的前缀又是s[0..2]的后缀，同时希望其长度尽可能长。是的，s[0..j]就是s[0..2]的最长相等前后缀。也就是说，只有令j=next[2]，然后判断s[5]==s[j+1]是否成立。如果成立，说明s[0..j+1]是s[0..5]的最长相等前后缀，令next[5]=j+1即可；如果不成立，就不断让j=next[j]，直到j回退到-1，或中途s[5]==s[j+1]成立。如下   图j从2回退到next[2]=0，发现s[5]==s[j+1]不成立，就继续让j从0回退到next[0]=-1；由于j已经回退到-1，因此不再继续回退。这时惊喜地发现s[i]==s[j+1]，说明s[0..j+1]是s[0..5]的最长相等前后缀，于是令next[5]=j+1=-1+1=0。

下面总结next数组的求解过程，并给出代码，读者可以结合上面的例子理解：

(1)初始化数组next，令j=next[0]=-1

(2)让i在1~len-1范围内遍历，对每个i，执行(3)(4)，以求解next[i]

(3)不断令j=next[j]，直到j回退到-1，或是s[i]==s[j+1]成立。

(4)如果s[i]==s[j+1]，则next[j]=j+1;否则next[i]=j

void getNext(string s){	int i,j;	j=next[0]=-1;//初始化数据next 	for(i=1;s[i];i++){		while(j!=-1 && s[i]!=s[j+1]){			j=next[j];		}		if(s[i]==s[j+1]){			j++;		}		next[i]=j;	}}
KMP
在此前的基础上，正式进入KMP算法的学习。你会发现，有了上面的基础，KMP就是在依样画葫芦。此处给出一个文本字符串text和一个模式串pattern,然后判断pattern是否是文本字符串text的子串。以text="abababaabc" 、pattern="ababaab"为例。令i指向text的当前欲比较位，令j指向pattern中当前已被匹配的最后位，这样只要text[i]==pattern[j+1]就说明pattern[j+1]也被成功匹配，此时继续让i、j加1比较，直到j到达m-1时说明pattern是text的子串 。如下图所示，i=4之前都成功匹配了。此时i指向text[5]、j指向pattern[4]，标明pattern[0..4]已被成功匹配。于是尝试判断text[i]==pattern[j+1]是否成立，如果成立，则pattern[0..5]被匹配成功，可令i、j加1继续匹配下一位，但十分不幸，此处text[5]!=pattern[4+1]，匹配失败。似乎很让人懊恼，难道要放弃之前的pattern[0..4]的成功匹配结果，让j回退到-1重新匹配吗？当然不是，只有暴力的做法才那么做！
那么该怎么做呢？为了不让j直接回退到-1，应该寻求回退到一个离当前j最近的位置j'，使得text[i]=pattern[j'+1]能够成立，并且pattern[0..j']仍然与text的相应位置处于匹配状态，即pattern[0..j']是pattern[0...j]的相同前后缀。这很容易令人联想到之前求next数组的类似问题。答案是pattern[0..j']是pattern[0...j]的最长相等前后缀。也就是说，只有不断令j=next[j]，直到j回退到-1或者text[i]==pattern[j+1]成立，然后继续匹配。从这个角度讲，next数组的含义就是当j+1位失配是，j应该回退的位置！
下面总结KMP算法的一般思路：
(1)初始化next数组和j=-1,表示pattern当前已经被匹配的最后一位
(2)让i遍历文本text，对每个i，执行(3)(4)来试图匹配text[i]和pattern[j+1]
(3)不断令j=next[j]，直到j回退到-1，或是text[i]==pattern[j+1]成立。
(4)如果text[i]==pattern[j+1]，则j++。如果j到底m-1，说明pattern是text的子串，返回true。
bool KMP(string text,string pattern){	getNext(pattern); //计算pattern的next数组	int j=-1;	int p_len=pattern.length();	for(int i=0;text[i];i++){		while(j!=-1 && text[i]!=pattern[j+1]){			j=next[j];		}		if(text[i]==pattern[j+1]){			j++;		}		if(j==p_len-1){//匹配成功			return true;		}	}	return false;}
接着如果要统计pattern在text中出现了多少次，只有在j==p_len-1的时候进行累计即可，但问题在于，这之后应该从模式串的哪个位置开始下一次匹配。通过上面的分析，可以联想到next[j]，因为此时的next[j]代表整个模式串pattern的最长相等前后缀，从这个位置可以让j最大，即让已经匹配的部分最长，这样既保证不漏解，又是下一次的匹配省去了许多没有意义的比较。
if(j==p_len-1){//匹配成功	count++;	j=next[j]}