理解数据结构教材中--KMP算法

1.一篇博文

KMP算法是一种字符串匹配算法，第一次接触KMP算法是在数据结构的教材中。为了弄懂这个算法，我在网上查阅了很多资料，很多博文都说其内容很好理解，但本人看完总是似懂非懂。
这个算法在掌握后会觉得非常简单，可其描述总是有些令人难以理解，这里推荐一篇2013年的文章，相信你看完后一定能理解KMP算法。
KMP算法博文
不过有一个问题是，此理解方法似与《数据结构与算法(第四版 廖明宏)》中的P63页对于KMP算法的解释有所出入。

2.书中解释

对于书中的解释，其重点为一个公式：
N e x t [ j ] = { 0 , j = 1 M a x { k ∣ 1 < k < j } , S u b s t r ( T , 1 , k − 1 ) = S u b s t r ( T , j − k + 1 , k − 1 ) 1 , 其他情况 Next[j]=

$$\begin{cases} 0,&\text{$j=1$}\\ Max\{k|1<k<j\},&\text{$Substr(T,1,k-1)=Substr(T,j-k+1,k-1)$}\\ 1,&\text{其他情况} \end{cases}$$ Next[j]=⎩⎪⎨⎪⎧​0,Max{ k∣1<k<j},1,​j=1Substr(T,1,k−1)=Substr(T,j−k+1,k−1)其他情况​
注：

• 书中的字符串第一个字符的索引位是1。
• 函数$Substr(T,n,m)$的含义是：对于字符串T，从第n位开始，截取m个字符。也就是截取一段字符串。
• 举例：$t[20]="8hellotom"$，$Substr(t,2,4)="ello"$. $t[0]$存放字符串长度，因此第一个字符的索引位是1。

模式串 $t$ 的每一个 $t_j$ 都对应一个 $k$ 值，此 $k$ 值仅依赖于模式串 $t$ 本身字符序列的构成，而与主串 $s$ 无关。用 $next[j]$ 表示 $t_j$ 对应的 $k$ 值。

3.对比书与博文

我们先以简单的语言来概括书与博文的要点。

• 书中，重点为公式：
  $Substr(T,1,k-1)=Substr(T,j-k+1,k-1)$
• 博文中，我们不妨用$table[j]$来表示部分匹配表，这个表中的部分匹配值就是前缀和后缀的最长的共有元素的长度。

这里我们用一个例子来说明：

模式串 $t="abaabcac"$ 或可写成 $t="8abaabcac"$，求其$next$和$table$

书中：

博文：

初看，我们会感觉$next$和$table$毫无关联，于是我们就会思考为什么是这个结果。
其实很好理解，在博文中提到了所谓的部分匹配表的用法：

模式串移动位数 = 已匹配的字符数 - 最后一个正确匹配位对应的 $table$ 值

而这个$table$表的含义是：前缀和后缀的最长的共有元素的长度。

再看书中公式：$$Substr(T,1,k-1)=Substr(T,j-k+1,k-1)$$
相信大家都感觉到了，这个公式中的 k-1也隐含表达：前缀和后缀的共有元素的长度，再加上一个 M a x { k ∣ 1 < k < j } Max\{k|1<k<j\} Max{ k∣1<k<j}，即表示最长的共有元素的长度。

• 其中前缀为：$t_1$~ $t_{k-1}$，后缀为：$t_{j-k+1}$ ~ $t_{j-1}$
• 并且其最长的共有元素的长度为：$k-1$，而这同时也是$table$表的含义。即 $k-1=table[j]$，即 $next[j]-1=table[j]$。

然而我们对上述两表根据 $next[j]-1=table[j]$ 关系对照发现，笑死，根本对不上。

其实只是因为我们忽略了一个小问题：
对于公式：前缀为：$t_1$~ $t_{k-1}$，后缀为：$t_{j-k+1}$ ~ $t_{j-1}$
我们发现后缀的结尾是 $t_{j-1}$ 而不是 $t_j$ ,这就是问题所在。相信看到这里童鞋们一定恍然大悟了，没错，我们得错开一位。
对于$next$表，它的第 $j$ 位的公式对应的后缀是 $t_{j-1}$ ，也就是对应$table$表的第 $j-1$ 位。即有对应关系：$$next[j]-1=table[j-1]$$

如此看来：
$table[1]=0=next[2]-1=1-1$
$table[2]=0=next[3]-1=1-1$
$table[3]=1=next[4]-1=2-1$
$table[4]=1=next[5]-1=2-1$
$table[5]=2=next[6]-1=3-1$
$table[6]=0=next[7]-1=1-1$
$table[7]=1=next[8]-1=2-1$
table[8]=0=next[9]-1=???-1
好的，现在都对应上了。。。除了$next[9]$不存在，也就是$table[8]$对应不上，这又是为什么呢？

我们要理解$table$表的用法，当 $t$ 有一位和主串 $s$ 不同，而之前都相同，此时就要用到$table$表。我们不妨设不同的那位是 $t_k$ 。现在计算模式串需要移动的位数：

模式串需要移动的位数 = 已匹配位数 - 最后一个正确匹配位对应的 $table$ 值

即： $移动位数=(k-1)-table[k-1]$。

好，现在回归之前的问题：$table[8]$对应不上。
我们看看什么情况下才会用到 $table[8]$ ，$k=9$时对吧，可是模式串一共只有8位，第9位根本不用考虑！

明白了吧，其实 $table[8]$ 根本就用不到，我们不求它都可以。

唉，好像又出现了个问题，就是当模式串 $t$ 的首位就与主串 $s$ 不同，这时我们用公式：

模式串需要移动的位数 = 已匹配位数 - 最后一个正确匹配位对应的 $table$ 值

已匹配位数为0，最后一个正确匹配位对应的 $table$ 值没有定义。这就是问题所在。
解决方法很简单：

1. 我们给 $table[0]$ 定义为 -1。并且其仍满足 $next$ 与 $table$ 的对应关系： $table[0]=-1=next[1]-1=0-1$。
   这样需要移动的位数 = 0 - (-1) = 1位 。。。 over
2. 在代码中遇到这种情况，仅需用if判断出来，然后手动令其移动1位即可。。。over

好了，至此就没啥问题了。总结来看，KMP算法是利用了模式串本身存在的重复性进行优化的，这种重复性即前缀后缀那里。似乎很好理解。

4. 代码

既然博文与教材并不冲突，那么下面给出利用 $table$ 表实现KMP算法的c语言代码。其优点就在于 $table$ 表的计算很好理解，即前缀和后缀的最长的共有元素的长度。

• 代码中的索引用$t_0$代表第一个字符

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void my_gettable(char *t,int table[]);
int my_kmp(char *s,char *t,int table[]);

int main(){
   
	char s[20]="abaabcaabaabcaca",t[20]="abaabcac";
	int table[20];
	int i,m;
	my_gettable(t,table);
	for(i=0;i<strlen(t);i++)
		printf("table[%d]=%d\n",i,table[i]);
	m=my_kmp(s,t,table);
	if(m==-1)
		printf("没找到！");
	else
		printf("首次出现索引：%d",m);
	
	return 0;
}

void my_gettable(char *t,int table[]){
   
	int i,j=0,k,m;
	for(i=0;i<strlen(t);i++){
   
		table[i]=i;
		k=j+1;
		while(k<=i){
   
			for(m=k;m<=i;m++){
   
				if(t[j]!=t[m]){
   
					table[i]--;
					break;	
				}
				else
					j++;
			}
			j=0;
			k++;
			if(m==i+1)
				break;
		}
	}
}

int my_kmp(char *s,char *t,int table[]){
   
	int i=0,j=0;//i为s的指针，j为t的指针 
	while(i<strlen(s) && j<strlen(t)){
   
		if(s[i]==t[j]){
   
			i++;
			j++;
		}
		else if(j==0)//这就是上面提到的用if判断出来，手动加1的地方
			i++;
		else 
			j=table[j-1]; //这里很好理解，不必考虑什么递归思想什么的。
			//先按照博文思路，计算出模式串需要移动的位数，已匹配位数：j ，所以移动位数m=j-table[j-1].
			//接下来可以自己画图理解：把串后移m位，相当于把串t的指针前移m位。即j=j-m=j-(j-table[j-1])=table[j-1]
	}
	if(j<strlen(t))
		return -1;
	else
		return i-strlen(t);
}

---

转载：https://blog.csdn.net/qq_43475997/article/details/113823216