菜狗的KMP学习

为什么我们要学习KMP呢?这就不得不说起当年暑假在校队集训的时候,苦逼做不出题目的痛苦时光了。

三个人看着题目中字符串匹配的那个环节,思索了整整三个小时。

不得不说,从0到1,远比在前人的肩膀上前行要难得多。真不知的这些变态大佬是怎么想出来的。

先来提及一下,当时我们用人脑想出来的代码(我没有说他们不是人:对于大部分人来说,那肯定就是一个个照着去比对就行了,然而很遗憾的是:

可惜时间太短,我无法爱上你——超时......

这就是那所谓的BP算法

1.朴素模式匹配(BP)

由于这个真的太基础,懒得废话了。就是应该去主串和模式串一个个去配对,如果该字符匹配,则j++,否则j=0,然后i++

int index_BP(string s,string p){
	int sl=s.length(),pl=p.length();
	for(int i=0;i<=sl-pl;i++){
		int flag=1;
		for(int j=0;j<pl;j++){
			if(s[i+j]=!p[j]){
				flag=0;
				break;
			}
		}
		if(flag)
		return i;
	}
	return -1;
}

2.KMP算法(三个人名...)

(1)前缀与后缀

什么是前缀和后缀捏?

ju个栗子,比如说有个字符串“abac”,那么对于该字符串而言,“a”,“ab”,“aba”则是它的前缀(PS:严格来讲,“abac”和空串也可以算作前缀)。

相应的,对于后缀而言就是,“c”,“ac”,“bac”等。

(2)next数组

这个时候,可能就会想前后缀和字符串的匹配有什么关系呢?其实,重点就在于信息的重复利用。

比如说,对于模式串“abdad”而言,如果在第5个字符“d”的时候不匹配,那么我们不需要再次去重头可以匹配,因为对于字符串“abda”而言,有相同的前后缀“a”。

所以我们只需要从“b”开始进行相应的配对即可。

从这里就可以看出,KMP算法实质就是利用当前字符前的字符子串的相同前后缀,来跳过大量没有意义的重复匹配。

这个是相关的动画。。。有点丑,而且有点慢,但是,菜狗的我不会调速度

接下来就是求next数组了,next数组是利用模式串得到的。

那为什么要叫做next数组呢?那是因为如果当前字符不匹配,下一个要比对的模式串的字符是哪个。

相应的计算公式如上所示。

(3)相关的代码

int mynext[200000];
void get_next(string s){
	int l=s.size(),k=-1;
	mynext[0]=-1;
	for(int i=1;i<=l;){
		if(k==-1||s[i]==s[k]){
			i++;k++;
			mynext[i]=k;
		}
		else k=mynext[k];
	}
}
int index_kmp(string s,string p,int pos){
	int i=pos,j=0;
	int sl=s.size(),pl=p.size();
	for(i=pos,j=0;i<sl&&j<pl;){
		if(j==-1||s[i]==p[j]){
			i++;j++;
		}
		else j=mynext[j];
	}
	if(j>=pl) return i-pl;
	else return -1;
}

3.相关例题

P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Password - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

热门相关:我的女友不可能是怪物   我有无数神剑   极品妖孽归来   灭世之门   公子别秀