第2章第3节练习题2 串的模式匹配(KMP)
最后更新于：2022-04-01 19:51:54
## 问题描述
设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。
## 算法简述
在[练习题1](http://blog.csdn.net/u013595419/article/details/50533721)中的算法是最简单的模式匹配算法，但是该种算法每当匹配失败时，对主串已经匹配过的字符又需要重新匹配一次，时间复杂度为O(n2)。因此这里引入了KMP算法。KMP算法与[第2章第3节练习题1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)中算法最大的不同便是重新创建了一张跳转表，而且使得主串仅可以访问一次，子串可以一次跨过多个元素进行比较。为了从总体上来说明该算法，这里举个例子：
主串S：babcbabcabcaabcabcabcacabc
子串T：abcabcacab
在有些书中将子串T也称为模式串，但这都不重要，本讲解称其为子串。首先给出经过优化后的跳转表（next），从整体上简单的梳理下执行过程。
- **跳转表（next）**
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 |
| **T[j]** | a | b | c | a | b | c | a | c | a | b |
跳转表最大的特色就是决定了子串一次性可以跳过多少个元素与主串进行比较，跳转表的作用是前*`next[j]-1`*个元素组成的字符串和第j号元素之前(不包括第j号元素)的*`next[j]-1`*个字符串相等，这么听起来比较抽象，举个简单的例子说明下，比如以 j=8为例。
当j=8时，查得next[8]=5，则可以推出前4个元素和第8号(不包括第8号元素)元素前面的4个元素相等。
即：T[1]T[2]T[3]T[4]组成的字符串“abca”与T[4]T[5]T[6]T[7]组成的字符串“abcd”相等。
这里简写为T1,2,3,4=T4,5,6,7
不失一般性，进行一次推广，得到广义的公式。这里令k=next[j]，即
T1,2,...,k−1==Tj−(k−1),j−(k−2),...,j−1
- **执行过程**
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c |
| **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | |
| **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | |
| **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | |
| **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | |
| **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | |
| **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | |
这里应该特别注意的是主串和子串的下标标号方式不同，**主串下标从0开始，子串下标从1开始**。
- 第一轮比较中，T[1]!=S[0]，查找跳转表得`next[1]=0`此时便可以得出子串的第一个元素与此时主串的元素不匹配，对主串的下一个元素进行比较；
- 进入第二轮比较，当比较到T[4]时，发现T[4]!=S[4]，查找跳转表得`next[4]=0`，原因同上，对主串的下一个元素进行比较；
- 进入第三轮比较，当比较到T[8]时，发现T[8]!=S[12]，查找跳转表得`next[8]=5`，进入下一轮比较；
- 进入第四轮比较，由上轮比较中得到`next[8]=5`，比较T[5]与S[12]，结果发现T[5]!=S[12]，查找跳转表得`next[5]=1`，进入下轮比较；
- 进入第五轮比较，由上轮比较中得到`next[5]=1`，比较T[1]与S[12]，然后发现T[1]=S[12]，开始挨个比较，比较到T[8]时，发现T[8]!=S[19]，查找跳转表得`next[8]=5`，进入下轮比较；
- 进入第六轮比较，由上轮比较中查找过程得到`next[8]=5`，比较T[5]与S[19]，结果发现T[5]=S[19]，开始逐个比较；
- 最后子串T与主串S全部比较完成，返回结果。
这里便可以推出KMP算法的核心执行步骤为：
- 如果j==0，则表明子串的第一个元素不满足，则将主串的下一个元素与子串的第一个元素相比；
- 如果S[i]==T[j]则开始比较下一个元素，即S[i+1]与T[j+1]；
- 如果不相等，则比较S[i]与T[next[j]]；
## 算法详解
在`算法简述`中，简单的梳理了下执行流程，也推出了KMP算法的核心步骤，与[第2章第3节练习题1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)并无太大差异，只是如果不相等的时候，并不需要对主串S的下标重置，而是对子串T进行移位便可。而真正的难点便是建立跳转表（next），因为满足跳转表（next）的元素有一个非常重要的特性便是：
T1,2,...,k−1==Tj−(k−1),j−(k−2),...,j−1
而且由上面的特性很容易发现，当第j号元素与主串相应的元素“失配”时，才需要在子串中重新置位与主串再次相比，这里便引出跳转表（next）的定义：
~~~
next[j] =
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪0,max{k|1length;j++){
for(k=1;kdata[i]==T->data[j-k+i]&&ilength){
if(T->data[i]==T->data[j]||j==0){
++i;
++j;
next[i]=j;
}else{
j=next[j];
}
}
}
~~~
最后再将主串S和子串T从头比较一次，熟悉下整个流程，过程如下：
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c |
| **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | |
| **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | |
| **T** | | | | | a | | | | | | | | | | | | | | | | | | | | | |
| **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | |
| **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | |
| **T** | | | | | | | | | | | | a | b | | | | | | | | | | | | | |
| **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | |
| **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | |
### 思想3
上面虽然已经完成了建立跳转表，使用KMP算法完成了子串的查找，但是通过分析就可以发现，建立跳转表完全可以再优化一次，即一步到位。
- 主串S[4]与子串T[4]完全可以不需要，因为T[4]==T[1]，已经判断出T[4]!=S[4]，也就无需在额外的判断T[1]!=S[4]了；
- 主串S[12]与子串T[2]亦完全可以不要 ，原因同上，已知T[5]==T[2] ，也就无需判断T[2] !=S[12]了；
先对跳转表完成优化，如下所示：
- **跳转表（next）**
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 |
| **T[j]** | a | b | c | a | b | c | a | c | a | b |
- **执行过程**
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 |
|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|
| **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c |
| **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | |
| **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | |
| **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | |
| **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | |
| **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | |
| **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | |
对上述过程进行总结，完成对算法的优化，描述如下：
~~~
void BuildNext(String* T, int next[])
{
int i, j;
i=1;
j=0;
next[1]=0;
while(ilength){
if(T->data[i]==T->data[j]||j==0){
++i;
++j;
if(T->data[i]!=T->data[j]){
next[i]=j;
}else{
next[i]=next[j];
}
}else{
j=next[j];
}
}
}
~~~
至此，KMP算法的讲解算是完成了，具体代码见附件。
## 附件
~~~
#include
#include
#define MaxSize 100
typedef char ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}String;
void StrCreatS(String*);
void StrCreatT(String*);
void Print(String*);
void BuildNext(String*,int*);
int KMP(String*,String*,int*);
int main(int argc,char* argv[])
{
String *s;
s=(String*)malloc(sizeof(String));
StrCreatS(s);
String *t;
t=(String*)malloc(sizeof(String));
StrCreatT(t);
int next[MaxSize]={0};
BuildNext(t,next);
int flag=KMP(s,t,next);
if(flag!=-1){
printf("Position is %d.\n",flag+1);
}else{
printf("Illege Find!\n");
}
return 0;
}
//创建主串
void StrCreatS(String* S){
char x;
S->length=0;
printf("Input String_S(End of '#'!):\n");
scanf("%c",&x);
while(x!='#'){
S->data[S->length++]=x;
scanf("%c",&x);
}
getchar();
}
//创建子串
void StrCreatT(String* S){
char x;
S->length=0;
printf("Input String_T(End of '#'!):\n");
scanf("%c",&x);
while(x!='#'){
S->data[++S->length]=x;
scanf("%c",&x);
}
getchar();
}
//打印字符串
void Print(String *S)
{
for(int i=0;ilength;i++){
printf("%c",S->data[i]);
}
printf("\n");
}
//建立跳转表
void BuildNext(String* T, int next[])
{
int i, j;
i=1;
j=0;
next[1]=0;
while(ilength){
if(T->data[i]==T->data[j]||j==0){
++i;
++j;
if(T->data[i]!=T->data[j]){
next[i]=j;
}else{
next[i]=next[j];
}
}else{
j=next[j];
}
}
}
//KMP算法的核心
int KMP(String* S, String* T,int next[])
{
int i=0, j=1;
while(ilength&&jlength){
if(S->data[i]==T->data[j]||j==0){
++i;
++j;
}else{
j = next[j];
}
}
if(j==T->length){
return i+1-T->length;
}else{
return -1;
}
}
~~~
参考文献
Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in Strings.[J]. Siam Journal on Computing, 1977, 6(2):323-350.
参考Blog
[http://blog.csdn.net/joylnwang/article/details/6778316](http://blog.csdn.net/joylnwang/article/details/6778316)
[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)
';