KMP算法（——模板习题与总结）

　　KMP算法是一种改进的模式匹配算法，相比于朴素的模式匹配算法效率更高。下面讲解KMP算法的基本思想与实现。

　　先来看一下朴素模式匹配算法的基本思想与实现。

　　朴素模式匹配算法的基本思想是匹配过程中如果该位置相等，继续匹配各自的下一位，直至匹配完成，或者出现一位不匹配，如果该位置不相等，主串的匹配位置返回上次开始匹配位置的下一位，副串的匹配位置再次从头开始。

实现程序如下：

　　主串s，副串t，如果存在，返回t在s中第一次出现的位置，否则返回-1。

 1 int Index(char *s,char *t){
 2     int ls=strlen(s),lt=strlen(t);
 3     int i=0;//主串匹配位置 
 4     int j=0;//副串匹配位置 
 5     while(i < ls && j < lt){
 6         if(s[i] == t[j]){
 7             i++;
 8             j++;
 9         }
10         else{
11             i=i-j+1;
12             j=0;
13         }
14     }
15     if(j >= lt)//副串匹配完成
16         return i-j;
17     else
18         return -1; 
19 }

　　可以设想，最糟糕的情况是每次的匹配的不成功均发生在了最后一位匹配，那么它的时间就主要浪费在了主串回溯的过程，比如00000001（7个0）和001，就有5次回溯是不必要的，它浪费的时间是随着匹配成功之间的0的个数增多而增多，自然就想到没有什么办法去解决这个问题呢？

　　下面就轮到KMP算法登场了。

　　为了解决每次主串匹配不成功不用回溯或者说尽可能不回溯的问题，就想到了用不用回溯和副串有什么关系。下面看一个例子

abcdefgh

abcz

按照之前的算法，会有如下的匹配过程：

①

abcdefgh

abcz

②

abcdefgh

abcz

③

abcdefgh

abcz

④

abcdefgh

abcz

⑤

abcdefgh

abcz

　　拿1和2来说，已知副串中ab第一位a和第二位b不相同，而副串和主串中前两位相同，可以知道副串中的第一位a和主串中的第二位b（也就是回溯的位置）肯定不相同，换句话说，这次回溯是可以避免的，同样的道理，匹配过程3也是可以避免的。再来研究一下这个规律，主串和副串的匹配过程中，要想不回溯，i的值是不能减少的，而j的值有和副串当前匹配的子串本身的重复有关系。

　　那么这个关系是什么呢？结论是跟这个子串的前后缀的相似度有关。

　　那么怎么计算一个子串的前后缀的相似度呢？

　　我们用next[j]数组来表示j下次应该返回的位置,函数定义如下：

　　next[j]= 0,当j=0

　　　　　　max({k|0<k<=j,且p0…pk=p(j-k)…pj}，当此集合不为空

　　　　　　1，其他

算法实现如下：

　　副串t，用next数组存储结果。

 1 void get_next(char t[],int next[])
 2 {
 3     int l=strlen(t);
 4     int i=0;//副串匹配位置 
 5     int j=-1;//next数组位置指针，初始化为-1，表示回溯边界 
 6     next[0]=-1;//0表示长度为0的子串的前后缀相似度为-1，也表示回溯边界
 7     while(i < l){
 8         if(j == -1 || t[i] == t[j]){
 9             i++;
10             j++;
11             next[i]=j;
12         }
13         else
14             j=next[j];
15     } 
16 }

下面将制作好的next数组应用到KMP算法中。

代码如下：

 1 int Index_KMP(char *s,char *t){
 2     int ls=strlen(s),lt=strlen(t);
 3     int i=0;//主串起始匹配位置 
 4     int j=0;//副串起始匹配位置
 5     int next[maxn]={0};
 6     get_next(t,next);
 7     while(i < ls && j < lt){
 8         if(j == -1 || s[i] == t[j]){//增加j==-1表示回溯到了边界的情况 
 9             i++;
10             j++;
11         }
12         else{ 
13             j=next[j];//j返回到合适的位置，而i不用改变 
14         }
15     }
16     if(j >= lt)//匹配完成
17         return i-j;
18     else
19         return -1; 
20 }