加载中…
个人资料
一叶知秋
一叶知秋
  • 博客等级:
  • 博客积分:0
  • 博客访问:425,158
  • 关注人气:82
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

KMP算法学习

(2013-05-09 08:13:24)
标签:

kmp

next

bf

it

分类: 数据结构与算法


 

最近在看数据结构与算法分析的书籍,期间,在串处理中认识了KMP算法这一变态级不好理解的经典算法。反复看了很多文章,终于搞清了一点头绪,现整理出来,以便后续复习查看。

 

待解决的问题

假设P为给定的子串(模式串)S是待查找的字符串(目标串),要求从S中找出与P相同的所有子串,这称为模式匹配问题。 (可以给出子串在S中的位置)

 

在介绍KMP算法之前,我们需要先了解下基本模式匹配算法:BF算法Brute-ForceKMP是对BF算法的一种改进。 

0,两种算法之间性能比较

BF算法的时间复杂度O(strlen(S) * strlen(P)),空间复杂度O(1)

KMP算法的时间复杂度O(strlen(S) + strlen(P)),空间复杂度O(strlen(P)) 

1BF算法:

1.1算法思想

BF算法将目标串S的第一个字符与模式串P的第一个字符进行匹配,若相等,则继续比较S的第二个字符和P的第二个字符;若不相等,则比较S的第二个字符和P的第一个字符,依次比较下去,直到得出最后的匹配结果。

BF算法中,如果当前字符匹配成功,即s[i] == P[j],令i++j++,继续匹配下一个字符;如果失配,即S[i] != P[j]需要让i++,并且j= 0,即每次匹配失败的情况下,模式串P相对于原始串S向右移动了一位。所以,在出现失配的情况时,BF算法目标串需要回溯。即:放弃掉前面比较过相等的字符,后移一位,和模式串首部重新开始比较。

 

1.2举例说明

    Sababcababa

    Pababa

 

i=4                     i=1

Sababcababa          Sababcababa

Pababa               P ababa

j=4                     j=0

P 串前面的部分ababS串的abab匹配,在比较i=4j=4的时候,出现失配。这个时候,P串后移一位,主串回溯,重新开始比较。i=i-j+1=1j=0

 

1.3实现代码

int BFMatch(char *s,char *p)

{  

    int i,j;  

    i=0;

    while(i<strlen(s))

    {

        j=0;

        while(s[i]==p[j]&&j<strlen(p))

        { 

            i++;

            j++;

        }

        if(j==strlen(p))

            return i-strlen(p);  //匹配成功 

        i=i-j+1;               //指针i回溯

    } 

    return -1;

}

 

2KMP算法

KMP算法之所以叫做KMP算法是因为这个算法是由KnuthMorris Pratt三个人共同提出来的,就取三个人名字的首字母作为该算法的名字。

其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题,只需确定下次匹配j的位置即可,使得问题的复杂度由O(m*n)下降到O(m+n) 

Sababcababa           Sababcababa    

Pababa                P  ababa

 

我们通过BF的例子来引出问题。在比较过程中失败的是P的第5个字符a,这表明P的前4个字符是成功的。观察模式P前面匹配的4个字符(abab)。发现abab的前缀ab和后缀ab相同,因此,如果将前缀的字符移动到现在后缀所在的位置必定是匹配的。因此,在下一次比较时候,可以将P向后移2个字符。

同样:

 

Saaebcaaebaf      Saaebcaaebaf     

Paaeba.           P     aaeba

 

在比较过程中P的第5个字符a出现失配,这表明P的前4个字符是成功的。观察模式P前面匹配的4个字符(aaeb)。发现aaeb的前缀和后缀没有相同的,模式P的第4个字符b在它的前3个字符(aae)中并未出现。所以s[3]肯定不等于P[0], P[1], P[2],因此,在下一次比较时候,至少要将P向后移4个字符;再看P的第一个字符与最后一个字符是相同的,因此将P右移4个字符后,再从第一个字符比较,肯定也是不等的。综上所诉:应该将P右移5个字符,再从P的第0个字符和T的第6个字符开始比较。 

2.1 KMP算法核心

KMP算法借助于一个辅助数组next来确定当匹配过程中出现不等时,模式P右移的位置和开始比较的位置。next[j]的取值只与模式P本身的前j+1项有关,而与目标串S无关。匹配过程中遇到Pj不等于Ti时,若next[j]>=0,将j值赋值为next[j],P中的第next[j]个字符与Si 进行比较.实现了将P右移j-next[j]个字符;若next[j]= -1,表明字符串P中的任何字符都不必再与Si比较,而应将P右移j+1个字符,从P0Si+1重新开始下一轮比较。

这里next[j]<=j-1,即模式串P相对于原始串S向右移动了至少1(移动的实际位数j-next[j]>=1) 显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用 

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

2.2 next数组的含义

令原始串为: S[i],其中0<=i<=n;模式串为: P[j],其中0<=j<=m

  假设目前匹配到如下位置

               S0,S1,S2,...,Si-j,Si-j+1...............,Si-1, Si, Si+1,....,Sn

                            P0,P1,....................,Pj-1, Tj, ..........

  SP的绿色部分匹配成功,恰好到SiPj的时候失配,如果要保持i不变,同时达到让模式串P相对于原始串S右移的话,可以更新j的值,让Si和新的Pj进行匹配,假设新的jnext[j]表示,即让Sinext[j]匹配,显然新的j值要小于之前的j值,模式串才会是右移的效果,也就是说应该有next[j] <= j -1。那新的j值也就是next[j]应该如何确定呢?我们观察如下的匹配:

      1)如果想要模式串右移1位,即next[j] = j - 1 即让蓝色的Sipj-1匹配

               S0,S1,S2,...,Si-j,Si-j+1...............,Si-1, Si, Si+1,....,Sn

                            P0,P1,....................,Pj-1, Pj, ..........

                               P0,P1,..................Pj-2,Pj-1, .......

        比较上图可以知道:当next[j] =j -1,即模式串右移一位的时候,有P[0 ~ j-2] == P[1 ~ j-1],而这两部分恰好是字符串P[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串Pj前面部分的前缀和后缀相等部分的长度。

      2)如果想要模式串右移2位,即next[j] = j - 2 即让蓝色的SiPj-2匹配    

               S0,S1,...,Si-j,Si-j+1,Si-j+2...............,Si-1, Si, Si+1,....,Sn

                         P0,P1,P2,........................,Pj-1, Pj, ..........

                               P0,P1,.....................,Pj-3,Pj-2,........

        同样可以知道:当next[j] =j -2,即模式串右移两位的时候,有P[0 ~ j-3] == P[2 ~ j-1]。而这两部分也恰好是字符串P[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串Pj前面部分的前缀和后缀相等部分的长度。

     3)依次类推,可以得到如下结论:当发生失配的情况下,j的新值next[j]取决于模式串中P[0 ~ j-1]中前缀和后缀相等部分的长度, 并且next[j]恰好等于这个最大长度。(K的值越大,相对意味越小,移位数为j – next[j],如果不是最大长度,可能移位过大,忽略部分匹配情况) 

2.3 next数组求法

第一种求法:(未优化)

对于next[]数组的定义如下:

   1) next[j] = -1         j = 0

   2) next[j] = max(k):    0<k<j   P[0...k-1]=P[j-k,j-1](前缀后缀相等的最大值)

3) next[j] = 0         其他

代码实现:

void getNext(char *p,int *next)

{

    int j,k;

    next[0]=-1;

    j=0;

    k=-1;

    while(j<strlen(p)-1)

    {

        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]

        {

            j++;

            k++;

            next[j]=k;

        }

        else                   //p[j]!=p[k]

            k=next[k];

    }

}

算法采用了递归的思想,

我们假设模式串为 ”ababdabac”,一步步分析:结果为-1,0,0,1,2,0,1,2,3

j=0时,说明第一个字符就不匹配,前面没有子串,遇到这种情况时,需要目标串和模式串都往后移一位。所以我们取next[0] = -1;

进入while循环,此时,j=0; k=-1;所以,j,k都加1j=1,k=0; next[1] = 0;(前面只有一个字符,所以肯定为0,前后缀都为null)

再次判断,因为p[1]!=p[0], 所以k=next[0]=-1;

出现了K=-1j,k1j=2,k=0; next[2]=0;

再次判断,因为p[2]=p[0], 所以,j,k1,j = 3,k=1;next[3]=1;

再次判断,因为p[3]=p[1], 所以,j,k1,j = 4,k=2;next[4]=2;

再次判断,因为p[4]!=p[2], 所以k=next[2]=0;

再次判断,因为p[4]!=p[0], 所以k=next[0]=-1;

出现了K=-1j,k1j=5,k=0; next[5]=0;

再次判断,因为p[5]=p[0], 所以,j,k1,j = 6,k=1;next[6]=1;

再次判断,因为p[6]=p[1], 所以,j,k1,j = 7,k=2;next[3]=2;

再次判断,因为p[7]=p[2], 所以,j,k1,j = 8,k=3;next[3]=3;

 

注意观察,我们可以知道,

上述,j表征的是模式串j前面的0~j-1长度为j的前缀的长度。K表征长度为j的串中前缀和后缀相等的长度(第0位到第k-1位),也就是相等前缀的最后一个字符+1

1)P[j]==P[k],则有P[0..k]==P[j-k,j],很显然,next[j+1]=next[j]+1=k+1;

2)P[j]!=P[k],比较新加入的字符和之前已经匹配的前缀的前缀有没有相等,即取k=next[k]

例子1

a b a c a b a a d  子串abacaba前缀和后缀相等的长度为3,当加入下一字a时,abacabaa因为ac不相等,所以此时取k=next[3]=1,即取之前取得的前缀中含有的相同前缀和后缀子串的个数,即aba中的前缀和后缀相同的长度1,然后再比较P[j]==P[k]?,依次递推。

例子2

AAA……….AAAB……..KKKKKKK…….AAA……….AAAB

在求B处的next值时,先看P[j]==P[k]?如果相等,那么next值加1

AAAB……….AAAC……..KKKKKKK…….AAAB……….AAAB

如果不相等,下一步需要比较前面黄色部分的前缀中的下一位和j位是否相等,如果相等,那么,则就是next[k]+1,如果不相等,继续递推

 

上述求法只是简单的求取模式串P的前缀和后缀相等的最大长度值k,没有优化。

 

第二种求法:(优化)

 

先看一个例子:

模式串Pabcabc,如果按照一中的算法,得到的next数组为{-1,0,0,0,1,2}

但是我们注意观察一下:

如下:

Sabcababcabc

Pabcabc

根据1的解法,应该后移3位,如下图所示

SAbcabaabcabc

P   abcabc

但是我们发现:刚开始S[5]=aP[5]=c是不等的,但是P[5]=P[2]=c,按照1中的做法,移位后肯定有S[5]!=P[2],所以这一次移位是无效的,还需要再做下一步:

SAbcababcabc

P     abcabc

即根据next[2]=0,P串后移两位,达到匹配成功。

所以,这里就存在着优化的空间。我们可以在计算next的时候,先比较一下S[j]==P[k]?

如果相等,即取next[j] = next[k],这样就可以把上述事例中的中间那一步省掉。

优化后的代码为:

void getNext(char *p,int *next)

{

    int j,k;

    next[0]=-1;

    j=0;

    k=-1;

    while(j<strlen(p)-1)

    {

        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]

        {

            j++;

            k++;

          if (p[j]==p[k])     //此处为优化部分,增加了一次判断。

               next[j]=next[k];

          else

            next[j]=k;

        }

        else                   //p[j]!=p[k]

            k=next[k];

    }

}

KMP算法实现:

OK,终于完了,直接上代码:

输出在目标串中找到模式串的位置

int KMPsearch(char* src, int slen, char* patn, int plen, int* next, int pos)   

{   

    int i = pos; 

    int j = 0;

      

    while ( i < slen && j < plen ) 

    {   

        if( j == -1 || src[i] == patn[j] ) 

        {   

            ++i;

            ++j;

        }   

        else 

            j = next[j];  //当匹配失败的时候直接用p[next[j]]s[i]比较,          

    }   

    if( j >= plen )

        return i-plen;

    else   

        return -1;

} 

 

参考文献:http://www.cppblog.com/oosky/archive/2006/07/06/9486.html

http://blog.csdn.net/v_july_v/article/details/7041827

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有