看毛片KMP算法
KMP算法作为一个单模式串匹配算法,以$ O(n+m) $ 的时间复杂度俯视众生吊打各路匹配算法
但是其扩展性的艰难和通用性的低下往往很少用于项目中的实现,但对于我们Oier来说速度才最重要的
KMP的代码量并不大,思维难度也并非其他玄学算法那么高,时间也很优秀,是一种值得用于搞事情的算法
算法理念
传统匹配
在普通的查询算法中,我们通常采用一下的方法:
int ans=0;
for(int i=0;i<alen;i++){
int t=0;
while(1){
if(t>=blen) break;
if(a[i+t]!=b[t]) break;
t++;
}
if(t>blen) ans++;
}
模式串: ab
文本串: fdsfdfdvab
emmmmm $ O(n) $??优秀
模式串: sb
文本串: sssa
$O(nm)$???什么状况?
好吧,我们知道了,这个东西最快$O(n)$,最慢…$O(nm)$
KMP匹配
显然如果我们在上面的第二个例子中
我们如果能知道,我现在失配了,应当直接更改当前s在模式串中的位置就可以高效的完成匹配
为此,我们定义一个next
数组,用「自己匹配自己」的思想,快速找到,当我们适配失败的时候,迅速找到这一位可能在模式串中的位置
这样就避免了往回的问题,大大降低了时间复杂度–$O(n+m)$
代码实现
题目链接: [https://www.luogu.org/problemnew/show/P3375]
#include <cstdio>
#include <cstring>
using namespace std;
int kmp[11000000];
char a[1100000],b[1100000];
int main(){
scanf("%s",a+1);
scanf("%s",b+1);
int alen=strlen(a+1);
int blen=strlen(b+1);
int k=0;
for(int i=2;i<=blen;i++){
while(k>0&&b[i]!=b[k+1]) k=kmp[k];
if(b[i]==b[k+1]) k++;
kmp[i]=k;
}
k=0;
for(int i=1;i<=alen;i++){
while(k>0&&a[i]!=b[k+1]) k=kmp[k];
if(a[i]==b[k+1]) k++;
if(k==blen) {printf("%d\n",i-blen+1);k=kmp[k];}
}
for(int i=1;i<=blen;i++) printf("%d ",kmp[i]);
}
KMP 求最小循环节
「KMP这个算法,一般很少考板子题,他通常会给你出一些思维型的,比如,next数组的妙用….」
Next
数组的思想不单在KMP
中很有用,在对付其他字符串处理问题甚至多模式串匹配中,我们仍将见到他的身影
比如求一个串的最小循环节
很显然len-next[len]
即为循环节长度
- 如果$ len \mod len-next_{len} = 0 $ 则表明字符串是完全由循环解循环构成
- 如果不是说明需要添加,如果设循环节长度为$L$,则添加的字母个数$ L-len%L = L-next[len]%L $
当然不止这些,至于还有什么吗wq你总会遇到的啦
End
最后,祝rp++
]]>
dalao,KMP的时间复杂度不是O(N+M)吗,似乎锅了…
已经发现,谢谢提醒,修改完毕