KMP模式匹配算法分析与实现
2009-04-17 20:03:39 来源：WEB开发网基本概念：
模式匹配是对字符串的一种非常重要的操作，假设被匹配的正文字符串是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++!='')
{
++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]==''||Text[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;
}
中查找“KMP模式匹配算法分析与实现”更多相关内容
中查找“KMP模式匹配算法分析与实现”更多相关内容
赞助商链接
