C++ Programmer

天行健,君子以自强不息; 地势坤,君子以厚德载物

KMP算法

   KMP 匹配算法是由 "Knuth  Morris  Pratt"  提出的一种快速的模式匹配算法。  
   hint:不为自身的最大首尾重复子串长度

   1.待解决的问题:假设P为给定的子串,T是待查找的字符串,要求从T中找出与P相同的所有子串,这称为模式匹配问题。 (可以给出子串在T中的位置) (下文中提到的P和T分别为子串和目标串)

   让我们先来看个例题:

   T:   t0      t1     t2      t3 .... tm-1 ... tn-1

   P:   p0      p1     p2      p3 .....pm-1         

                                               

   从T的最左边开始比较,使得 TK = PK,则匹配成功。

   2.解决模式匹配问题的方案:

   A:朴素的模式匹配算法(思路简单,但不够简便,时间长,有回溯):最简单和最直接的做法,用P中的字符依次与T中的字符进行比较,遇到不相等的字符,则可将P右移一个字符,重新进行比较,直到某次匹配成功或者到达P的最右字符移出T为止。

   如:若P="aaaba", T="aaabbaaaba", 则匹配过程如下图

    T:     a   a   a   b   b   a   a   a   b  a

    P:     a   a   a   b   a                                                                

               a   a   a   b   a                

                                   .....

                               a   a   a   b  a           

   从上不难分析,最坏的情况是“每次比较都在最后一个字符出现不等,每趟最多比较M次,最多比较N-M+1趟,总的比较次数最多为M*(N-M+1)” ,时间复杂性为0(M*N)。 在P右移一位时,不管上一趟比较的中间结果是什么,因此回溯是不可避免的(如:前3个aaa 不需要一位一位的移 ) 。下面我来介绍无回溯的KMP算法。

   3.KMP算法解决匹配中哪些主要问题:

   A.当字符串比较出现不等时,确定下一趟比较前,应该将P右移多少个字符; 

   B. P右移后,应该从哪个字符开始和T中刚才比较时不等的那个字符继续开始比较。

    我们通过朴素模式匹配的例子来引出问题。在第一次比较过程中失败的是P的第4个字符b,这表明P的前4个字符是成功的。模式P的第3个字符b在它的前3个字符(aaa)中并未出现。因此,在下一次比较时候,至少要将P向后移4个字符;再看P的第一个字符与最后一个字符是相同的,因此将P右移4个字符后,再从第一个字符比较,肯定也是不等的。综上所诉:应该将P右移5个字符,再从P的第0个字符和T的第5个字符开始比较!

   KMP算法核心:KMP算法借助于一个辅助数组next来确定当匹配过程中出现不等时,模式P右移的位置和开始比较的位置。next[i]的取值只与模式P本身的前i+1项有关,而与目标T无关。匹配过程中遇到Pi不等于Tj时,若next[i]>=0,则应将P右移i-next[i]位个字符,用P中的第next[i]个字符与Tj 进行比较;若:next[i]= -1,P中的任何字符都不必再与Tj比较,而应将P右移i+1个字符,从P0和Tj+1从新开始下一轮比较(可能不太好理解,自己找个例子,对着话一句一句试试看)

 

   因此只要计算出与模式P相关的next数组,按上面的含义,就可以很容易地给出串的匹配算法。(问题就这样转化了)

    C.next的计算:以P = " 01001010100001"为例。

     i   :            0   1   2   3   4   5   6    ..... 

     P   :            0   1   0   0   1   0   1    .....

    j(next[i]) :     -1   0   0   1   1   2   3    .....

   如1:我们要算next[2]的值,有关的为P本身的前2个字符0,1。在字符串01中,寻找出“左右相同的最大字符串,此字符串所含字符的个数就为next[i]的值”而0不等于1,相同字符串不存在,所以next[i] = 0;

   如2:我们要算next[6]的值,有关的为P本身前6个字符010010 。此字符串中010 = 010左右相同的最大字符串为010,个数为3。所以next[i]=3;

   如3:我们要算next[5]的值,有关的为P本身前5个字符01001。此字符串中 01=01 左右相同的最大字符串为01,个数为2。所以next[i]=2;

#include<stdio.h>
#include
<string.h>
#include
<stdlib.h>
FILE 
*fin=fopen("test.in","r");
FILE 
*fout=fopen("test.out","w");
char s1[200],s2[200];
int next[200];

int max(int a,int b)
{
    
if(a>b) return a;
    
return b;
}


void getnext()
{
    memset(next,
0,sizeof(next));
    
int i=-1,j=0;
    next[
0]=-1;
    
while(j<strlen(s2))
    
{
           
if(i==-1||s2[i]==s2[j]){
               i
++;  j++;  
               next[j]
=i;
           }

           
else i=next[i];
    }

}


int KMP()
{
    
int i=0,j=0,len1=strlen(s1),len2=strlen(s2);
    
while((i<len1)&&(j<len2))
    
{
        
if(j==-1||s1[i]==s2[j]) {j++;i++;}
        
else j=next[j];
    }

    
if(j==len2) return i-len2;
    
else return -1;
}


int index_KMP()
{
    
int i=0,j=0,len1=strlen(s1),len2=strlen(s2),re=0;
    
while(i<len1&&j<len2)
    
{
                         
if(j==-1||s1[i]==s2[j]) {i++;j++;}
                         
else j=next[j];
                         re
=max(re,j);
    }

    
return re;
}


int main()
{
    fscanf(fin,
"%s",s1);
    
for(int i=1;i<=3;i++)
    
{
            fscanf(fin,
"%s",s2);
            getnext();
            fprintf(fout,
"%d %d\n",KMP(),index_KMP());
    }

    
return 0;
}

posted on 2009-07-16 15:47 Saga 阅读(27686) 评论(18)  编辑 收藏 引用 所属分类: Algorithm

评论

# re: KMP算法 2009-07-16 18:18 乐蜂网

学东西了  回复  更多评论   

# re: KMP算法 2009-07-17 00:05 Chen Jiecao

KMP,高二的时候学的,看的是Matrix67的文章.膜拜Knuth!  回复  更多评论   

# re: KMP算法 2011-04-21 10:55 lstar

楼主这里有问题吧,
while(j<strlen(s2))
{
//临界条件 j=strlen(s2) -1;
if(i==-1||s2[i]==s2[j]){
i++; j++;
// j++后 j=strlen(s2);
//next[j] 数组越界了?
next[j]=i;
}
else i=next[i];
}
  回复  更多评论   

# re: KMP算法 2011-11-29 16:34 forget_x13

谢谢楼主分享,这里的kmp比其他的写得好的很多~~真心感谢!!!!@lstar
  回复  更多评论   

# re: KMP算法 2011-11-29 16:35 forget_x13

谢谢楼主分享,kmp比其他的写的好的太多,真心感谢~  回复  更多评论   

# re: KMP算法 2012-03-07 10:58 itmelody

送人玫瑰手有遗香,谢谢分享。  回复  更多评论   

# re: KMP算法 2012-03-26 11:18 lazier

感谢楼主的细心的讲解,讲的太细致了,谢谢~  回复  更多评论   

# re: KMP算法 2012-04-04 15:52 Sadoshi

@lstar
不会越界,因为第一个判断i==-1成立,就不会再判断后面的了  回复  更多评论   

# re: KMP算法[未登录] 2012-04-09 15:00 will

貌似确实越界了,运行了一下 用了len = 6 (abaaba)的字符串 ,但是求next时循环中的j可以达到6,这应该算是越界了吧@Sadoshi
  回复  更多评论   

# re: KMP算法 2012-05-06 01:44 该是天才

当模式匹配不成功时,上面程序会出错。原因如下:strlen返回值是unsigned型,而j是signed型,所以cout<<(-1<strlen(s));结果会是0,而不是1。 上面程序里的strlen(s)都应该改成(signed int)strlen(s)  回复  更多评论   

# re: KMP算法 2012-05-06 01:56 该是天才

unsigned int a=3;
cout<<(-1<a);
int 隐式转换为 unsigned int 所以-1就变成0xFFFFFFFF=4294967295  回复  更多评论   

# re: KMP算法 2012-05-25 01:22 annoymous

确实会越界,但是不是楼上说的那种原因造成的。仔细看求解next数组的函数,while循环里的条件比较的是j,j的初始值是0.而j在循环体中要么不变,要么递增,所以不可能变为-1。

至于越界的原因,考虑那位兄弟说的例子,我们在计算了next[5]=2之后,循环仍会执行,此时j=5<strlen("abaaba")=6,循环体再执行一次,得出next[6]=3。然后此时循环条件不再满足,结束循环。

这里多计算了一次,将while循环的条件改为j<strlen(s2)-1即可避免此种情况。  回复  更多评论   

# re: KMP算法 2012-05-27 02:08 annoymous

test  回复  更多评论   

# re: KMP算法 2012-05-31 17:25 f

赞楼主!!!  回复  更多评论   

# re: KMP算法 2012-08-23 17:04 huozhixinxin

虽然找前缀数组直观上交代的挺明白的,不过求前缀数组最关键的还是在它的迭代思想吧。楼主用了,但是文字上没怎么交代啊。。。  回复  更多评论   

# re: KMP算法 2013-01-10 15:46 xiaoq

我们通过朴素模式匹配的例子来引出问题。在第一次比较过程中失败的是P的第4个字符b,这表明P的前4个字符是成功的。模式P的第3个字符b在它的前3个字符(aaa)中并未出现。

这里有误吧。一会第4个,一会第3个  回复  更多评论   

# re: KMP算法 2013-01-10 15:49 xiaoq

@xiaoq

不好意思。是看错了。
但是第一次比较失败的是P的第4个字符a而不是b(b是主串的第4个字符)  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜