字符串算法~KMP
2021-04-23 03:29
标签:else eof clu == 判断 string 优化 arc ide 有个视频讲的挺好的: 传送门 首先给一个字符串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是匹配字符串; 字符串算法~KMP 标签:else eof clu == 判断 string 优化 arc ide 原文地址:https://www.cnblogs.com/whitelily/p/13270228.html字符串算法~KMP
#include