有人说 CCF 是 coin collect Federation (金币收集联会)。于是又说 KMP 是 kill my parents (杀掉我的父母)。好像有点阴森。。。话不多说,开始了。
KMP算法是一种改进的字符串匹配算法,由 D.E.Knuth,J.H.Morris 和 V.R.Pratt 提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称 KMP 算法)。KMP 算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 $\operatorname{next()}$ 函数实现,函数本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 $\mathcal{O}(m+n)$。
我们可以发现,KMP 的题目哈希似乎也可以做出来。但是我们可以发现,哈希其实有很多无用功。我们看下图:\
可以发现,在 c 的时候失配(失去匹配)了,但是前面的都符合。如果是哈希,就会像这样匹配:\
很明显,第 $2,4$ 次是无用功,而 KMP 就是为了避免这种无用功。具体是怎么避免的,请往下看。\
我们可以看到上图标红的区域其实是相同的,而第一次符合的就可以与自己本身所对应的先提前比较,避免浪费时间来处理整个的。\
那么怎么处理呢?我们需要用一个 $nxt$ 数组,而我们需要判断的就是,在一个固定的子串中,最长前后缀长度就是可以避免的。\
比如说下图:\
我们可以看到这一个字符串 $S$ 所对应的 $nxt$ 数组的数值其实是逐步递增的,那么我们就能得到一个 $\operatorname{getnext}$ 函数,如下:
void Get_Next(string x){
int i=0,j=-1;
nxt[0]=-1;
while(i<len2){
if(j==-1||x[i]==x[j]){
i++;
j++;
nxt[i]=j;
}
else{
j=nxt[j];
}
}
}
看完后发现并不难,接下来再附上 KMP 那一段代码,主要是运用 $nxt$ 数组,其实想一想并不难。
void kmp(string x,string y){
gn(y);
int i=0,j=0,ans=0;
while(i<len1){
if(j==-1||x[i]==y[j]){
i++;
j++;
}
else{
j=nxt[j];
}
if(j==len2){
ans++;
j=nxt[j];
}
}
}
本期例题较少,以理解为主。题单。
模板题,没得说。
#include<bits/stdc++.h>
using namespace std;
int len1,len2,nxt[1000005];
void gn(string x){
nxt[0]=-1;
int i=0,j=-1;
while(i<len2){
if(j==-1||x[i]==x[j]){
i++;
j++;
nxt[i]=j;
}
else{
j=nxt[j];
}
}
}
void kmp(string x,string y){
gn(y);
int i=0,j=0;
while(i<len1){
if(j==-1||x[i]==y[j]){
i++;
j++;
}
else{
j=nxt[j];
}
if(j==len2){
cout<<i-j+1<<"\n";
j=nxt[j];
}
}
}
int main(){
string x,y;
cin>>x>>y;
len1=x.size();
len2=y.size();
kmp(x,y);
for(int i=1;i<=len2;i++){
cout<<nxt[i]<<" ";
}
return 0;
}
用栈来维护 KMP 的操作,对于后退时不一定要全退,注意就好了。
#include<bits/stdc++.h>
using namespace std;
int len1,len2,nxt[1000005];
int st[1000005],top,ss[1000005];
void gn(string x){
nxt[0]=-1;
int i=0,j=-1;
while(i<len2){
if(j==-1||x[i]==x[j]){
i++;
j++;
nxt[i]=j;
}
else{
j=nxt[j];
}
}
}
void kmp(string x,string y){
gn(y);
int i=0,j=0;
while(i<len1){
if(j==-1||x[i]==y[j]){
st[++top]=i;
ss[i]=j;
i++;
j++;
}
else{
j=nxt[j];
}
if(j==len2-1){
top-=len2;
j=ss[st[top]];
}
}
}
int main(){
string x,y;
cin>>x>>y;
len1=x.size();
len2=y.size();
kmp(x,y);
for(int i=1;i<=top;i++){
cout<<x[st[i]];
}
return 0;
}
留做练习。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int len1,len2,nxt[1000005];
void gn(string x){
nxt[0]=-1;
int i=0,j=-1;
while(i<len2){
if(j==-1||x[i]==x[j]){
i++;
j++;
nxt[i]=j;
}
else{
j=nxt[j];
}
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cout.tie(0)->sync_with_stdio(0);
cin>>len2;
string x;
cin>>x;
gn(x);
int ans=0;
for(int i=1;i<=len2;i++){
int j=i;
while(nxt[j]){
j=nxt[j];
}
if(nxt[i]){
nxt[i]=j;
}
ans+=i-j;
}
cout<<ans;
return 0;
}
到此为止。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。