kmp

问题描述
给定一个主串S和模板串T，问T是否是S的子串？如S="aabcaad",T="caa"，则T是S的子串， T=S[3,5],（我们这篇博文字符串下标一律从0开始）。

算法描述
最直接的方法是枚举S的每个位置作为开始位置，然后从i向后依次比较每个字母是否相等。设S的长度为n，T的长度为m，则这个方法的复杂度为O(nm)。

kmp方法解决这个问题跟上述方法有个区别，就是指向S的指针i不回溯。比如说，在某次比较中，我们发现S[i]!=T[j]，那么i保持不变，T串向右滑动一段距离，用T的第k个字符与S的第i个字符比较(显然k小于j)。

那么满足什么样的关系时才能这样呢？由于S前面一段跟T[j]的前面相等，那么有S[i-j,i-1]=T[0,j-1]，并且由于S[i]能直接与T[k]比较，那么S[i-k,i-1]=T[0,k-1]，由于S[i-k,i-1]=T[j-k,j-1]，所以T[0,k-1]=T[j-k,j-1]。并且没有比k更大的值p满足T[0,p-1]=T[j-p,j-1]。我们定义这个的值为next[j]，它表示当T的第j个字符与S的某个字符匹配失败时，我们可以直接用T的第next[j]个字符与S的该字符比较。换句话说，我们还可以这样理解next[j]，它表示最大的满足T[0,k-1]=T[j-k,j-1]的k值。

我们先不管这个next数组是怎么计算的，对于串S="abaabcac"，它的next数组为：

有了这个next数组，我们寻找T是否是S子串的方法：

 1 /**
 2 返回T在S中第一次出现的位置
 3 没有 则返回-1
 4 */
 5 int kmpMatch(char s[],int lenS,char t[],int lenT,int next[])
 6 {
 7     int i=0,j=0;
 8     while(i<lenS)
 9     {
10         if(j==-1||s[i]==t[j]) i++,j++;
11         else j=next[j];
12         if(j>=lenT) return j-lenT;
13     }
14     return -1;
15 }

下面，我们来看如何计算next数组。我们来递推计算next，首先next[0]=-1,并且我们计算出了0到j的next值，设k=next[j]，那么有T[0,k-1]=T[j-k,j-1]。现在我们来计算next[j+1]的值。有两种情况。
第一种情况，T[j]==T[k]，此时有T[0,k]=T[j-k,j]，所以此时next[j+1]=k+1,也就是说next[j+1]=next[j]+1。
第二种情况，T[j]!=T[k]，那么我们需要找一个最大的x，使得T[0,x-1]=T[j-x+1,j]，那么next[j+1]=x。怎么找呢？由T[0,x-1]=T[j-x+1,j]，可以得到 T[0,x-2]=T[j-x+1,j-1],设y=x-1，那么我们需要找到这样一个y，y满足T[0,y-1]=T[j-y,j-1]并且T[y]=T[j]，那么y一定是next[j]，next[next[j]],...，中的从前向后第一个满足T[y]=T[j]的。
下面是计算next的代码：

 1 void getNext(char s[],int len,int next[])
 2 {
 3     next[0]=-1;
 4     int i=0,j=-1;
 5     while(i<len)
 6     {
 7         if(j==-1||s[i]==s[j]) next[++i]=++j;
 8         else j=next[j];
 9     }
10 }

到此我们就说完了kmp的所有东西。但是，上面求出的next数组有一些缺陷。我们设T="aaaab"，那么我们求出的next如下：

那么在匹配的时候，我们假设匹配到T[3]的时候失配了，那么按照next数组，接下来，我们将比较T[2]和S的那个字母，很明显又失败了(因为T[2],T[3]都是a)，接着比较T[1],T[0]，依次都失败了。这就是出现的问题。针对这个问题，我们对next数组进行以下改进：

 1 void getNext_1(char s[],int len,int next[])
 2 {
 3     next[0]=-1;
 4     int i=0,j=-1;
 5     while(i<len)
 6     {
 7         if(j==-1||s[i]==s[j])
 8         {
 9             i++; j++;
10             if(s[i]!=s[j]) next[i]=j;
11             else next[i]=next[j];
12         }
13         else j=next[j];
14     }
15 }

对于T="aaaab"求出的next数组为：