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

核心提示：基本概念：模式匹配是对字符串的一种非常重要的操作，假设被匹配的正文字符串是text，KMP模式匹配算法分析与实现，模式串是pattern，则模式匹配的任务就是在text中找出所有的pattern， int Patternlen=CharLen(Pattern);//模式字符串长度， int *prefix=new i

基本概念：

模式匹配是对字符串的一种非常重要的操作，假设被匹配的正文字符串是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;
}