转载

kmp算法

kmp

为了实现复杂度低的字符串匹配算法，将依次顺序的扫描算法O(n*m)的复杂度降到O(n+m) 的算法就有了kmp(knut-Morris-Pratt算法)。

字符串匹配，简单的来说就是在母串S中寻找是否含有模式串T，这种字符串匹配是计算机的基本任务之一。

kmp算法不易理解，网上有很多解释，读起来都很难以理解，看到了一个很好地总结http://kb.cnblogs.com/page/176818/ 现在真正的看懂理解了这种算法，下面在结合这篇博文的基础上进一步讲解一下基本kmp实现过程中的代码如何理解，和kmp的优化如何实现。

首先简单介绍一下博文中的对kmp的理解：

博文中讲解的顺序查找的算法和优化思想不再赘述，对博文中的部分匹配值得理解做详细描述，引入next数组的概念，要理解

1. 正确理解前缀和后缀的意思，eg： ABCD的前缀分别是A， AB ， ABC ， ABCD

后缀分别是 D ， CD ， BCD ， ABCD。注意，千万不可以把后缀理解成从后往前读的字符子串，这里明确一点：前缀一定是要包含当前字母前面的所有的字符，后缀一定要包含当前字符后面的所有的字符，这样对于next数组后面的解释才能正确理解其在整个算法中的作用。

2. 从next数组的定义上来理解：next[i]表示的是i位置前的串中，所有前缀和后缀中最长共有元素的长度，也可以说是共有元素长度中的最大值，引用博文中也有具体举例。（注意：同引用博文不同的是这里我们为了方便代码书写，所有的串下标默认从0开始编号，所以请仔细理解公共长度，这样方便与第二种next的用法上的理解对应）

在理解了前缀和后缀后进一步的解释后，next数组为什么要这么定义，首先，简单的理解就是i位置前的next[i]个字符和从开头数的next[i]个字符是一样的，那么匹配的时候如果是从i 处失配了，那么说明前面的所有部分都是已经匹配好的，那么现在如果前面的next[i]个字符和最后匹配好的字符是完全一样的就可以直接将这next[i]个放到这后面next[i]个位置上，即从第next[i]个位置从新开始匹配，那么就不需要移动母串的指针，直接将子串滑动到第next[i]的位置。下面看一个例子

母串 ABCAB C FGABABD

模式串 ABCAB D

标红地方失配了，而失配处前面的AB是已经匹配好的，根据前面的讲解，模式串应该滑动到下面的位置

母串 ABCAB C FGABABD

模式串 AAAAB C ABD

2. 有了这些知识我们来理解next数组的另一种理解，即next数组在算法中具体应用的理解：next[i]表示在i处失配话将

当失配的时候模式串要定位在模式串的第next[i]的位置上，这里要注意到上面提到的理解公共长度的部分，公共长度，由于数组标号是从0开始的所以失配位置要是想从新定位，看上面的例子可以理解应该是定位在相同部分的后一个位置，而后一个位置的下标刚好是公共长度（自己仔细思考，不再赘述）

那么，问题来了，怎样求next呢？（大致思路就是如何求最大的前缀和后缀的共有元素长）

我们先来给出代码，然后再一点点理解

1 int kmp(char* s , char* t)  2 {  3     int len1 , len2;  4     len1 = strlen(s);  5     len2 = strlen(t);  6     int i , j = 0 , tm = next[0] = -1;  7     //求next数组  8     while(j<len2-1){  9         if(tm<0||t[j]==t[tm]) 10             next[++j] = ++tm; 11         else tm = next[tm]; 12     } 13     //匹配 14     for( i=j=0 ; i < len1 && j < len2) 15     { 16         if(j<0||s[i]==t[j]) i++,j++; 17         else j = next[j]; 18     } 19     return i-j; 20 }

可以看到kmp算法的代码很短，我们先来分析求next数组的部分

1 //求next数组 2     while(j<len2-1){//依次求出模式串中每一个位置上的next值,循环j-2次即可，因为每次j是先++后处理的，相当于这个循环求出了下标从1到n-1位置的next值，下标为0的已经初始化时候定义过了 3         if(tm<0||t[j]==t[tm])//tm<0是为了让刚开始进入循环的时候不出错 4             next[++j] = ++tm; 5         else tm = next[tm]; 6     }

测试（可输出）

1 #include<cstdio>  2 #include<cstring>  3 #include<string>  4 using namespace std;  5 int next[1500];  6 int i , j = 0;  7 int tm = next[0] = -1;  8 int get_next(char* t)  9 { 10     int len = strlen(t); 11     while(j<len-1){ 12         if(tm<0||t[j]==t[tm])//tm<0是为了当找不到任何前缀等于后缀，而且不是字符串第一个字符的时候next值是0 13             next[++j] =++tm;//j和tm先加1再赋值，保证每次比较的字符串都不包含最后一位 14         else tm = next[tm];//如果这一位适配了，那么说明失配的字符前面的是已经匹配好的，然后要找失配位置的前面的字符串的next，即失配前的字符串中前缀等于后缀的长度 15     } 16 } 17 int main() 18 { 19     char s[10]; 20     scanf("%s",s); 21     get_next(s); 22     for(int i= 0 ;i < strlen(s);i++) 23         printf("%d ",next[i]); 24     puts(""); 25     return 0; 26 }

现在来分析一下求next主要代码

if(tm<0||s[j]==s[tm]) {j++,tm++; next[j]==tm;}

else tm = next[tm];

举例来说：其实可以将求next的过程看成是第二次的kmp匹配过程。

abcabfabcabg...

开始j定位到 a bcabfabcabg...

tm = -1,然后j和tm先++，然后就next[1] = 0——相应的对应b前面的字符串的公共前后缀长度为0，注意这里next[0]= -1是初始化了的；

然后比较 a b c abfabcabg...发现不匹配，然后让tm = next[tm]，这里不易理解这个语句的用途，下面一直分析，分析到

当要比较abcab f abcab g ...发现不匹配，这时候tm = 5 ; j = 11;发现不匹配，由于next的连续性，所以从第一个字符开始到f的所有字符，和从g前面数相同数目的字符肯定是匹配好的，这里要仔细理解next数组的含义，即前缀和后缀的公共最大长度，所以这里找f前面的字符的next数组，这里表示的是f前面的

ab c ab f abc ab g ...由于g前面的和f前面的是已经匹配好的所以粉色的表示f的已匹配的前缀，即长度为next[5]的长度，肯定等于黄色的ab（根据next定义）也定于绿色的ab（由于g和f之前是匹配好的）那么就相当与是ab在f和g之前就不用再考虑了，下次比较的时候就是g和橘黄色的c开始比较了

那么问题自然来了，有人会问如果串时这样的呢。。。。。注释1；

a b ca b f abca e g ...那么我们要想其实在绿色的部分已经失配了，即当tm = 4 ; j = 10 ; 的时候就已经失配了，那么tm 要跳到next[4] = 1 ，指向黄色位置

然后下次是tm = 1和j = 10 比较，即每次都是tm 向前跳而j 不变，然后发现tm = 1和tm = 10仍然不一样，所以跳到tm = next[tm] = 0 ,仍然失配，然后跳到tm = -1 ；

所以串在匹配的时候从abcabfabcabg...只要是一失配就向前跳一直跳到-1或者是满足注释1的地方，所以，只要是tm和j比较的时候一定是可以保证tm前面到串开始和从j前面的相同个数的字符是完全相同的。

现在就可以理解了next的数组了，如果不能理解，请再仔细阅读一遍，仔细思考。

下面我们来说一下一个简单的优化

假设在模式串的第i个位置失配，并且t[i] = t[next[i]]，那么令j= next[j]时依然失配，所以此时优化方法是令next[j] = next[next[j]].代码如下

1 int kmp(char* s , char* t)  2 {  3     int len1 , len2;  4     len1 = strlen(s);  5     len2 = strlen(t);  6     int i , j = 0 , tm = next[0] = -1;//初始化为-1为了，当第一个都不匹配的  7     //求next数组  8     while(j<len2-1){//依次求出模式串中每一个位置上的next值,循环j-2次即可，因为每次j是先++后处理的，相当于这个循环求出了下标从1到n-1位置的next值，下标为0的已经初始化时候定义过了  9         if(tm<0||t[j]==t[tm]){//tm<0是为了让刚开始进入循环的时候不出错 10             ++j;++tm; 11             if(next[j]==next[tm]) tm = next[tm];//优化 12             next[j] = tm; 13         } 14         else tm = next[tm]; 15     } 16     //匹配 17     for( i=j=0 ; i < len1 && j < len2) 18     { 19         if(j<0||s[i]==t[j]) i++,j++; 20         else j = next[j]; 21     } 22     return i-j; 23 }

1 //求next数组优化代码  2  8     while(j<len2-1){//依次求出模式串中每一个位置上的next值,循环j-2次即可，因为每次j是先++后处理的，相当于这个循环求出了下标从1到n-1位置的next值，下标为0的已经初始化时候定义过了  3  9         if(tm<0||t[j]==t[tm]){//tm<0是为了让刚开始进入循环的时候不出错  4 10             ++j;++tm;  5 11             if(next[j]==next[tm]) tm = next[tm];//优化  6 12             next[j] = tm;  7 13         }  8 14         else tm = next[tm];  9 15     } 10 16     //匹配

正文到此结束