KMP算法之我见

KMP算法之我见,第1张

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

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存