笔者初学kmp算法,发现该算法形式简单的背后包含着丰富的数学逻辑和原理。
这算是1.0版本,等后续笔者理解加深后会做出改进
凑合着看吧
a串(主串,文本串):n个字符
b串(模式串):m个字符
暴力算法:
枚举主串起始位置i,从此开始逐位与模式串比对,每一位都相同则匹配成功,否则一旦出现不同,使起始位置i+1,并从头开始模式串的匹配,时间复杂度为O(nm)
每次匹配失败后i和j都回溯从头匹配
,做了许多重复计算,无法汲取上次匹配失败的教训,当数据规模为1e5时会超
KMP算法核心思想:
利用匹配失败后的信息,尽量减少模式串与主串匹配次数
字符串的前后缀:
举个例子对于字符串asdfghjkl
它的前缀集合为:a,as,asd,asdf,asdfg,asdfgh,asdfghj,asdfghjk
它的后缀集合为:l,kl,jkl,hjkl,ghjkl,fghjkl,dfghjkl,sdfghjkl
不包含这个字符串整体
a串:abababaababacb
b串:ababacb
当匹配发生失败时,这个失败的信息不单单只代表在某位失败,还代表匹配失败的前面面的字符都匹配成功了
匹配失败后我们保持i不变,将b串向后移动,但不是一位一位的去移动(那样就是暴力了)。而是移动到有可能匹配成功的位置。
分为两种情况,
第一种情况是将b串最左端移动到i,不管i之前的字符了,从i开始作为起点重新匹配
第二种是将b串的最左端移动到i之前的位置:
我们把成功匹配的公共部分分别叫做a子串和b子串
当且仅当a子串的后缀集合与b子串的前缀集合有交集时,比如aba是公共的前后缀,就可以将b字串移动2位使交集相互匹配。
i因此不需要回溯,只需要j回溯了。
关于b串往后移动位数,也就是j指针回溯位置:
在已经获得的信息中做到不遗漏的同时尽可能的多匹配
于是,我们就要找到a子串后缀与b子串前缀的最长公共前后缀
只有这个最长的元素才能使b串后移的位数最少,在已知信息中匹配的最多,才能做到不遗漏每一种情况
因此这个最长公共前后缀的长度,就是j指针回溯的位置
另外由于a子串与b子串完全相同,所以只需要找出b子串的最长公共前后缀即可
j指针回溯的位置=b子串的最长公共前后缀,即j指针回溯的位置只和b
串有关,和a串无关
所以我们可以在ab串进行匹配之前对b串进行预处理,计算出回溯位置存放到一个数组next中
next数组与b串数组形成一一对应的映射,next[i]就是从b[1]到b[i]的最长公共前后缀长度
a,b串匹配的步骤(先假设已经获得next数组,之后会说next数组的构造)
i,j初始化为0
1:如果a[i+1]=b[j+1],i,j继续匹配
2:如果a[i+1]!=b[j+1],j回溯至next[j],直到a[i+1]=b[j+1].
当j回溯至0时也不能满足a[i+1]=bj+1即刚刚说的第一种情况
也就是说j=0时,忽略j增加i,直到a[i+1]=b[j+1]
3:j=m匹配成功,输出位置并继续匹配
next数组构造:模式串的自匹配
相当于b串与b串进行匹配
比如对于这个b串:
a b c a b e e e a b c a b c
next:
0 0 0 1 2 0 0 0 1 2 3 4 5 3
匹配失败next[i]=next[j]
匹配成功next[i]=next[i-1]+1
for(int i=2,j=0;i<=lenb;i++){
while(j&&b[i]!=b[j+1]) j=ne[j];
if(b[i]==b[j+1]) j++;
ne[i]=j;
}
总结:
时间复杂度是线性的O(m+n),
无论j如何回溯,i总是往前走的,即模式串整体是向前移动的(只不过移动多少的问题),只是模式串移动到主串尾部就算算法结束了
kmp一次比较只会产生两种结果
1:匹配成功:主串指针向前移动
2:匹配失败:模式串整体向前移动
前面主串移动必为n次,而后面的移动最多为n次,所以最大的时间复杂度为2n
同理也可得,构造next数组最大时间复杂度为2m
`