首页 > 代码库 > 【数据结构和算法】：KMP模式匹配算法

【数据结构和算法】：KMP模式匹配算法

2024-11-15 20:20:39   202人阅读

 Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。整个KMP的重点就在于当某一个字符与主串不匹配时，我们应该知道j指针要移动到哪里。

技术分享

如图：C和D不匹配了，我们要把j移动到哪？显然是第1位，因为如下面蓝框所示，前面A已经匹配。

技术分享

下面也如此：

技术分享

可以把j指针移动到第2位，因为前面有两个字母是一样的

技术分享

至此我们得知，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。

用数学公式表示如下：
P[0 ~ k-1] == P[j-k ~ j-1]

可以通过递推求得next 数组，代码如下所示：

01 void Next(char* p,int next[])  
02 {  
03     int pLen=strlen(p);  
04     next[0]=-1;  
05     int k=-1;  
06     int j=0;  
07     while (j<pLen-1)  
08     {  
09         //p[k]表示前缀，p[j]表示后缀  
10         if (k==-1 || p[j]== p[k])  
11         {  
12             ++k;  
13             ++j;  
14             next[j]=k;  
15         }  
16         else  
17         {  
18             k=next[k];  
19         }  
20     }  
21 }

next[j]的值（也就是k）表示，当P[j] != T[i]时，j指针的下一步移动位置。

当j为0时，如果这时候不匹配,j已经在最左边了，不可能再移动了，这时候要应该是i指针后移。所以在代码中才会有next[0] = -1;这个初始化。

技术分享

P[k] != P[j]

技术分享

从代码上看应该是这一句：k = next[k];为什么是这样子？你看下面应该就明白了。

技术分享

有了next数组之后就一切好办了，我们可以写KMP算法了：

01 int KmpMatch(char* s,char* p)  
02 {  
03     int i=0;  
04     int j=0;  
05     int sLen=strlen(s);  
06     int pLen=strlen(p);  
07     while (i<sLen&&j<pLen)  
08     {  
09         //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
10         if (j==-1 || s[i]== p[j])  
11         {  
12             i++;  
13             j++;  
14         }  
15         else  
16         {  
17             //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
18             //next[j]即为j所对应的next值        
19             j=next[j];  
20         }  
21     }  
22     if (j==pLen)  
23         return i-j;  
24     else  
25         return -1;  
26 }

备注：KMP算法是经典算法，原理和一些框图参考了网上的技术博客，这里融入自己的一些理解记录，以加深自己对算法的理解，同时与广大网友交流，欢迎批评指正！

【数据结构和算法】：KMP模式匹配算法


联系
我们