ID #5725

KMP模式匹配算法分析与实现

基本概念:

模式匹配是对字符串的一种非常重要的操作,假设被匹配的正文字符串是 text,模式串是pattern,则模式匹配的任务就是在text中找出所有的pattern, 给出pattern在text中的位置。

例如:text是“cdghcdghhcdr”,pattern是“cd”, 则答案是0,4,9(下标计数从0开始)

简单字符匹配:

第1轮:

用pattern的第1个字符与text的第1个字符比较,不等就结束,相等就

用pattern的第2个字符与text的第2个字符比较,不等就结束,相等就 ……

第2轮:

用pattern的第1个字符与text的第2个字符比较,不等就结束,相等就

用pattern的第2个字符与text的第3个字符比较,不等就结束,相等就 ……

……

这种做法非常直观,实际上就是把模式串pattern放到正文text的各个位置逐 一匹配,假设text、pattern的长度分别是m、n,则上述做法总共有m轮,每一轮 比较n次,所以该算法的时间复杂性是O(mn)。

KMP模式匹配:

简单匹配法在一次字符比较失败后,只是向前移动一个位置,丢掉了由前面 已做过的字符匹配的信息,当模式串pattern后面部分与前面部分有重复(匹配 )时,一次可以移动多个位置。

考虑如下例子:

表1

位置i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
正文text c a g a c a g a c a g a t a    
模式pattern a g a c a g a t a              

模式pattern后面有aga(第4到第6)与最前面aga(第0到第2)重复(匹配)

位置0不匹配,从位置1开始,匹配在正文text的第8个位置失败,如表2:

表2

位置i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
正文text c a g a c a g a c a g a t a    
模式pattern   a g a c a g a t a            

因为已经知道了pattern第4到第6个字符与最前面第0到第2个字符匹配,所以 下面的匹配过程直接移动4个位置,并且用pattern的第3个字符与text的第8个字 符开始比较,如表3。

表3

位置i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
正文text c a g a c a g a c a g a t a    
模式pattern           a g a c a g a t a    

实现kmp算法,需要一个临时数组存放支持匹配过程的有关信息,这个数组称 为前缀数组,它是一个整数数组,大小等于模式串pattern的长度,前缀数组不 妨定义为prefix[i],设prefix[i]==j,则prefix[i]表示从模式串pattern的第i 个位置(包括i)开始倒数共j个字符,这段字符与pattern的最开始j个字符相同 。prefix[i]称为前缀计数(也可以叫它匹配长度),它也可以认为从模式串 pattern[i](包括pattern[i])开始倒数到pattern[1]的范围内可匹配的长度。 注意,这个倒数的范围不能到第 0 个位置,否则所有的prefix[i]=i+1。如表4 。

表4

位置i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
前缀prefix[i] 0 0 0 0 1 2 3 1 2 3 4 5 6 7 4 0
模式pattern a g c t a g c a g c t a g c t g

例如,从表4可知,prefix[14]倒数的范围应该是从prefix[14]到prefix[1] ,逐一判断是否与最开始的1、2、3…14个字符相同,最终的结果是4,即 prefix[14]==4,表示从位置14开始(包含14),倒数4个字符(即agct)与 pattern最开始的4个字符相同。实际的处理中,无需判断14次那么多,我们后面 的算法中可看出来。

前缀数组的作用是指出当前字符匹配出现失败时如何处理。例如在表4中当匹 配在模式串pattern的第10个位置失败时,prefix[9]==3告诉我们在模式串 pattern的第10个位置之前的匹配有3个字符(其实就是第7到第9)与最前面的3 个字符匹配,因此可以从模式串pattern中的第4个字符(就是pattern[3],即t )开始比较下去。

下面重点考虑前缀数组prefix的初始化,这个乃是KMP的精华所在啊,很多人 对kmp的不理解也就在这个地方。

首先,显然有prefix[0]=0;假设字符数组模式串pattern的长度为patlen, 下面先给出代码1:

代码1:

prefix[0]=0;

for(int i=1; i<patlen; i++)

{

       int k=prefix[i-1];

       while( pattern[i] != pattern[k]  &&  k!=0 )
              k=prefix[k-1];
       if( pattern[i] == pattern[k])
              prefix[i]=k+1;
       else
              prefix[i]=0;
}

假设现在要设置prefix[i]的值,有两种情况:

情况1:对应字符互相匹配,prefix[i]的值可在prefix[i-1]的基础上加1;

情况2:对应字符不匹配,不能在原有基础上加1,需确定新的前缀计数。注 意,新的前缀计数不一定是从0或1开始计数,例如表4中prefix[14]是从4开始新 的前缀计数。

按照如上分析,貌似代码应该写成如下形式:

代码2:

prefix[0]=0;
for(int i=1; i<patlen; i++)
{
       int k=prefix[i-1];
       if( pattern[i] == pattern[k])
              prefix[i]=k+1;
       else
              其它处理;
}

例如表4中处理到prefix[14]时,发觉prefix[13]的前缀计数是7,就用 pattern[14]与pattern[7](即pattern[k])进行比较,相同则prefix[14]=7+1 ,不同就做其它处理。这样写代码也可以,但是后面的“其它处理” 同样有pattern[i] 与pattern[k]的比较,写起来反而复杂。

现在重点分析代码1,主要是里面的while循环较难理解。

while有2种走法:

第一种:一开始就有pattern[i] == pattern[k],也就是情况1里的对应字符 互相匹配,然后流程就进入后面的if,前缀计数加1,这种情况最易理解。

第二种:一开始pattern[i] != pattern[k],表示前缀计数不能加1,需重新 计数,令k=prefix[k-1],这里使用了一个技巧。

以表4中prefix[14]为例(此时i=14),prefix[13]==7表示前缀计数为7,或 者说从pattern[13]开始倒数7个字符(包括pattern[13])与最开始的7个相同, 即:

pattern[7]到pattern[13]  与

pattern[0]到pattern[6]   相同

下面就要判断

pattern[7]到pattern[14]  是否与

pattern[0]到pattern[7]   相同? 因为pattern[14]!=pattern[7],这表 示,前缀计数为8是不可能的了。下面需确定新的前缀计数,不管新的前缀计数 是多少,它都必须从pattern[14]开始倒数x个字符(包括pattern[14])来判断 是否与最开始的x个字符相同。而x的取值范围并不是从1到13,也就是说并不需 要从pattern[14]倒数到pattern[1]。要从pattern[14]开始倒数,也可以先看看 pattern[13]开始倒数能有多少个字符与最开始的相同,只是此时倒数的极限是 pattern[8](即只能数7-1=6个字符来判断,如果数到pattern[7],将变成 prefix[13],那么又要判断前缀计数能否是8了),同时,我们发现

pattern[7]到pattern[13]  与

pattern[0]到pattern[6]   相同

从pattern[13]开始倒数到pattern[8]与从pattern[6]倒数到pattern[1]是等 价的,而从pattern[6]倒数到pattern[1]的前缀计数prefix[6]早已求出。

因此:从pattern[14]开始倒数,等于从pattern[13]开始倒数prefix[13]-1 个字符的前缀计数(暂记为p,这个前缀计数等于prefix[ prefix[13]-1 ],都 是倒数prefix[13]-1个字符,早已求出),再比较pattern[14]与pattern[p], 相同,退出while循环,那么pattern[14]的前缀计数就是p+1;如果不相同,那 么while循环继续,倒数p-1个字符,递归处理。

下面总结一下并向代码1的符号靠拢:要计算prefix[i],先赋值k=prefix[i -1],当pattern[i] != pattern[k]时,表示prefix[i]要重新确定前缀计数,这 个前缀计数等于从pattern[i-1]开始倒数k-1个字符(数到pattern[i-k+1])范 围内所得的前缀计数(因为pattern[i-k]到pattern[i-1]刚好等于pattern[0] 到pattern[k-1],而从pattern[k-1]数到pattern[1]范围内的前缀计数早已求出 ,就是prefix[k-1]),重新赋值给k,然后再次比较pattern[i]与pattern[k], 如果仍然不相等,则从pattern[i-1]开始倒数k-1个字符(此时的k是新的值), 同理,前缀计数等于prefix[k-1],循环直至pattern[i]与pattern[k]相同或 k==0;最后,总的前缀计数等于新的前缀计数再加上判断pattern[i]与pattern [k]的计数,相等则为k+1,不相等为k(此时k必为0)。

int k=prefix[i-1];// 先赋值k=prefix[i-1]
/////////////////////////////////////////////////////////////////
while( pattern[i] != pattern[k]  &&  k!=0 )// pattern[i] != pattern[k]时
              k=prefix[k-1];// 前缀计数等于…所得的 前缀计数…就是prefix[k-1], 重新赋值给k

然后再次比较pattern[i]与pattern[k],如果仍不等,则从pattern[i-1]开 始倒数k-1个字符(此时的k是新的值),同理,前缀计数等于prefix[k-1],循 环直至pattern[i]与pattern[k]相同或k==0;

///////////////////////////////////////////////////////////// ////
//总的前缀计数等于新的前缀计数再加上判断pattern[i]与pattern[k]的计数

//相等则为k+1,不相等为k(此时k必为0)。

if( pattern[i] == pattern[k])
              prefix[i]=k+1;
       else
              prefix[i]=0;

写下这些,我基本上明白了,但就这么简单的几句代码,我绞尽脑汁却无法 把它描述得更简单。事实上,精华就是一句话:假设前一个前缀计数是p,新的 前缀计数是q,则q必然不能超过p,或者说,新的前缀必须是前一个前缀的前缀 ,因此,只需从前一个前缀的倒数位置(即当前位置的前一个位置)开始倒数p -1个字符来判断就可以了,而从前一个前缀的倒数位置开始倒数p-1个字符效果 等同于从p-1位置开始倒数p-1个字符来判断,即q= prefix[p-1],天呀,这句精 华怎么还是这么长?

再讲述一下表4的例子:

prefix[7]:因为prefix[6]=3,因此要判断前缀计数是否为4,即判断 pattern[3]与pattern[7]是否相同,结果不同,于是从pattern[6]开始倒数 prefix[6]-1=2个字符,即倒数pattern [6]、 pattern [5],它的效果与从 pattern [prefix[3-1]]开始倒数2个字符,即倒数pattern [2]、 pattern [1] 是一样的,而从pattern [prefix[3-1]]开始倒数的前缀计数就是prefix[3-1], 这个是前面计算的结果,就是0,再判断pattern [0]与pattern[7],结果相同, 于是prefix[7]=1;

prefix[14]:和上面类似,要判断前缀计数是否为8,先判断pattern[7]与 pattern[14]不同,于是从pattern[13]开始倒数prefix[13]-1=6个字符,效果等 同从pattern[6]开始倒数6个字符所得到的前缀计数,即prefix[6]=3,然后判断 pattern[3]与pattern[14]相同,于是prefix[14]=4;

prefix[15]:要判断前缀计数是否为5,先判断pattern[4]与pattern[15]不 同,于是从pattern[14]开始倒数prefix[14]-1=3个字符,效果等同从pattern [3]开始倒数3个字符所得到的前缀计数,即prefix[3]=0,然后判断pattern[0] 与pattern[15]不同,此时代码1中的k==0,于是prefix[15]=0。

注:本文prefix数组与许多其它文档资料提到的next数组的意义是一样的, 只是表示方法有所不同,并且不同的表示方法有一些优劣区别,就不深究了,你 也可以简单看一下这篇文章KMP字符串模式匹配详解,简单的介绍了3种表示方法 ,大多大同小异,若看不到图,你可以看这里:KMP字符串模式匹配详解。

以下给出完整源代码:

#include <iostream>
using namespace std;
//求字符串长度
int CharLen(const char *Text)
{
     if( !Text )
         return -1;//空指针返回-1。
     int len=0;
     const char * c=Text;
     while(*c++!='\0')
     {
         ++len;//字符串长度。
     }
     return len;
}
//设置前缀数组
void SetPrefix(const char *Pattern, int prefix[])
{
     int len=CharLen(Pattern);//模式字符串长度。
     prefix[0]=0;
     for(int i=1; i<len; i++)
     {
         int k=prefix[i-1];
         while( Pattern[i] != Pattern[k]  &&  k!=0 )
              k=prefix[k-1];
         if( Pattern[i] == Pattern[k])
              prefix[i]=k+1;
         else
              prefix[i]=0;
     }
}
//KMP模式匹配
int KMP(const char *Text,int pos,const char* Pattern)
{
     if( !Text||!Pattern|| Pattern[0]=='\0'||Text[0]=='\0' )
         return -1;//空指针或空串,返回-1。

     int Patternlen=CharLen(Pattern);//模式字符串长度。
     int *prefix=new int[Patternlen+1];
     SetPrefix(Pattern,prefix);//求Pattern的前缀数组
     int Textlen=CharLen(Text);
     int patp=0;//模式中的位置
     for(int i=pos;i<Textlen;i++)
     {
          while(patp>0 && Pattern[patp]!=Text[i])
              patp=prefix[patp-1];//第patp个位置与Text[i] 不同,则可从prefix[patp-1]这个位置开始比较
                                 //而不 需要直接从模式串的第个位置开始比较
         if(Pattern[patp]==Text[i])//模式串与正文中的一个字符 相匹配
         {
              //匹配长度加后判断是否等于模式串的长度,若 等于则返回相应的位置
              if(++patp==Patternlen)
              {
                   return i-Patternlen+1;
              }
         }
     }
     delete []prefix;
     prefix=0;
     return -1;
}
 int _tmain(int argc, _TCHAR* argv[])
{
     char *text="cabcdabcabcdaababcbaaabcdabcabcaabc";
    char *pattern="abcdabcab";
     int pos=-1;
     do
     {
         pos=KMP(text,pos+1,pattern);
         cout<<pos<<'\n'<<endl;
     }while(pos!=-1);
     return 0;
}


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

记录KMP算法,记录其经典之处

字符串近似匹配算法