字符串算法~KMP

2021-04-23 03:29

阅读:441

标签:else   eof   clu   ==   判断   string   优化   arc   ide   

字符串算法~KMP

有个视频讲的挺好的:

传送门

首先给一个字符串s,与另外一个字符串q,判断q是否是s的子串。

如何判断,先考虑暴力判断,枚举s字符串的每一位作为开头与q比较是否与q的每一位都相同,不相同及时break进入q的下一位继续从头开始比较,这样暴力判断其实也很快,一般情况下与KMP也没差多少,但是有部分样例,可以把暴力匹配的这种方式卡的很慢,比赛出KMP题的话,这种样例也是必有的。

举个栗子:s为aaaaazzzzz,q为aaaaaa;

s刚好少q一个a,那么基本上大多数的比较都是快吧q比较完了,结果最后不行,所以时间复杂度被卡成了O(N*M),N,M分别表示两个字符串的大小。KMP的在这里的作用就是用来快速过这种样例的,那么我们思考一下这种样例有什么特点,是不是q的a有点太多了,类似一种前后缀相似(像abcabcabc,azazaz也是如此),KMP就是利用了这种相似的特点。(先停一下,如果q没有这种相似那怎么办,放心q的相似越少,那么在与s比较的过程中大部分情况会越快被break掉,为什么的话可以自己想一想)。

现在我给一个新的样例来模拟一下:

s:1 2 1 2 3 1 2 3 1 3 2 1 2

q:1 2 3 1 3

第一次:1/1;

第二次:12/12;

第三次:12(1)/12(3);不同

第四次:(2)/(1);不同

第五次:1/1;

第六次:12/12;

第七次:123/123;

第八次:1231/1231;

第九次:1231(2)/1231(3);不同

这次不一样了,按理说我们要从s的第4位2继续找,但是我现在是不是知道s的第6位是1了,或者说s的第6位与q的第4位相等,因为在q的第5位,s的第7位不同,所以知道q的前4位与s对应相等,同时我如果我对q进行一些预处理的话,我也能知道q的第4(4至4位)位与其第1(1至1位)位相等及s的第6位与q的第1位相同,那么我们是不是可以直接拿s的第7位与q的第2位去比较了,跨过了s的4,5,6位以达到优化时间的目的,KMP的关键就是预处理next数组,总时间复杂度为O(n+m)。

next数组的目的再强调一边,找到对应位置往前最长的与前缀相同的长度,如abcdabc,最后一个c的可与前两个ab组成abc与前缀abc相同,next在第i位的意思是如果第i位发生错误(与比较字符串不同),前i-1位找到的前缀的末尾位置加一;

字符串: a b c d a b c @

数组为:-1 0 0 0 0 1 2 3

原理和表示说完了,之后就是模拟过程,不多说了,给个板子自己学一下:

第一个while是构造next数组,第二个while是匹配字符串;

#include
#include
using namespace std;

int t,n,m,a[1000007],b[100007],nextp[100007];

int kmp(int a[],int b[]){
	int l=-1,r=0;
	nextp[0]=-1;
	while(r

字符串算法~KMP

标签:else   eof   clu   ==   判断   string   优化   arc   ide   

原文地址:https://www.cnblogs.com/whitelily/p/13270228.html


评论


亲,登录后才可以留言!