转载

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     //匹配
正文到此结束
Loading...