KMP算法之我见

说来惭愧，一个考研狗在试图捡起数据结构准备复试的时候，居然觉得KMP算法有点难。昨天研究了一下午终于有点理解了，因此把心得体会写下来，方便日后复习。也欢迎各位在评论区指点
首先附上我的代码，已在某oj上运行通过

#include 
using namespace std;
char a[105],b[105];//a是主串，b是模式串
int n[105];//next数组，取名next的时候编译不通过，貌似是存在重名数组
void getnext(){
	int i=1,j=0;
	n[1]=0;//王道上KMP算法的下表从1开始，因此我从数组的下标为1
	while(istrlen(b+1)) printf("%dn",i-strlen(b+1));
		else printf("0n");
}
int main(){
	for(int k=1;k<=3;k++){
		memset(a+1,'',sizeof(a+1));
		memset(b+1,'',sizeof(b+1));
		memset(n,0,sizeof(n));
		scanf("%s",a+1);
		scanf("%s",b+1);
		getnext();
		kmp();
	}
	
}

kmp匹配与getnext（）其实大同小异，如王道所说，getnext()的过程其实也就相当于模式串自己对自己用了一次kmp匹配。但二者又有以下区别

循环终止条件不同

while(i 
这是因为next数组的第一个元素next[1]必为0，所以只需循环模式串长度-1次即可获得next数组
 
2.i与j的初始值不同
 
int i=1,j=1;//kmp()
int i=1,j=0;//getnext()
 
区别的原因在于，kmp()与getnext()当中i j的意义不同。
 对于kmp()而言，i与j分别是当前比较的主串和模式串的字符的下标（从1开始而不是从0开始）
 对于getnext()而言，i代表目前正在确认第几个元素的next数组值，j代表：如果匹配过程中，第i个元素发生失配，应该让位于第i元素之前的，第j个元素来匹配，也就是说，对于模式串而言，其第1至j-1个与第i-j+1至i-1个元素是完全相等的
 
总之，相比起简单模式匹配的“失配即清零”，kmp算法更加适用于主串与模式串存在多个“部分匹配”的情况。它保证了主串指针不回溯，失配时将模式串向后“拽”，使得模式串当中的某个元素与当前主串的字符匹配，而不是模式串的第一个元素
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702862.html