当前位置：首页 > news >正文

nefu暑假集训5 KMP 个人模板+例题汇总

news 来源：原创 2024/9/20 0:16:07

前言：

KMP算法用于匹配字符串，假设长字符串为s，需要匹配的字符串是p。KMP算法的基础思想是利用一个next[n]数组：next[i]对应的是：以下标i为结尾的连续子串，与以第一个字符开始的子串，相等的最大长度。该数组的作用是，当某一个下标的元素没有匹配成功时，可以通过该长度跳转到与匹配成功的部分字符串的最后一个，开始下一次匹配。以下是我写的一些题目。

正文：

链接：nefu-KMP - Virtual Judge (vjudge.net)

题目：

A - 剪花布条：

#include<bits/stdc++.h>
using namespace std;
string s,p;
int main(){while(cin>>s&&s!="#"){cin>>p;long long ans=0;while(s.find(p)!=-1) s.erase(s.find(p),p.length()),ans++;cout<<ans<<endl;}
}

这题好像根本用不上KMP，直接用string的find函数就能写出来。

B - Power Strings:

#include<bits/stdc++.h>
using namespace std;
int nxt[1000100];
char s[1000100];
int main(){while(~scanf("%s",s+1)&&s[1]!='.') {int n=strlen(s+1);nxt[1]=0;for(int i=2,j=0;i<=n;i++){while(j>0&&(j==n||s[i]!=s[j+1])) j=nxt[j];if(s[i]==s[j+1]) j++;nxt[i]=j;}if(n%(n-nxt[n])==0&&nxt[n]) printf("%d\n",n/(n-nxt[n]));else puts("1");}return 0;
}

这题实际上就是求字符串最大循环节问题，我们这边直接找到next数组中的next[n],n-next[n]就是他的最小循环子串，但是得判断一下是否可以由该字串直接完美构成（也就是n%(n=next[n])得是0）。

C - KMP：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s1[N],s2[N];
int ne[N];
int main(){cin>>s1+1>>s2+1;int n=strlen(s1+1),m=strlen(s2+1);//cout<<strlen(s1+1)<<" "<<strlen(s2+1)<<endl;for(int i=2,j=0;i<=m;i++){while(j&&s2[i]!=s2[j+1])j=ne[j];if(s2[i]==s2[j+1])j++;ne[i]=j;}for(int i=1,j=0;i<=n;i++){while(j&&s1[i]!=s2[j+1])j=ne[j];if(s1[i]==s2[j+1])j++;if(j==m){printf("%d\n",i-m+1);j=ne[j];}}for(int i=1;i<=m;i++){cout<<ne[i]<<" ";}return 0;
}

模板题。

D - Radio Transmission：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s[N];
int ne[N];
int main(){int l;cin>>l>>s+1;for(int i=2,j=0;i<=l;i++){while(j&&s[i]!=s[j+1])j=ne[j];if(s[i]==s[j+1])j++;ne[i]=j;}cout<<l-ne[l]<<endl;return 0;
}

最小循环子串=l-ne[l]，证明可以上网搜搜。

E - OKR-Periods of Words：

这题就是再求最短前缀，我们只需要在求完next数组后直接不断往前循环让next[i]=即可

F - 似乎在梦中见过的样子：

#include<bits/stdc++.h>
using namespace std;
const int N=150005;
char w[N];
int k,n,ans,ne[N],f[N];
int main(){scanf("%s%d",w+1,&k);int n=strlen(w+1);for(int i=1;i<=n;i++){int l=i-1;ne[i]=i-1;f[i]=i;for(int j=i+1;j<=n;j++){while(l!=i-1&&w[l+1]!=w[j])l=ne[l];if(w[l+1]==w[j])ne[j]=++l;else ne[j]=i-1;if(l<i+k-1)f[j]=j;else f[j]=f[l];ans+=(f[j]<((i+j)>>1));}}cout<<ans<<endl;return 0;
}

第一层循环枚举初始位置，第二层循环从每个位置开始做KMP，然后找到满足ABA且A>k的情况。

G - Censoring：

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s1[N],s2[N];
int ne[N],top,pos[N],stk[N];
int main(){cin>>s1+1>>s2+1;int n=strlen(s1+1),m=strlen(s2+1);for(int i=2,j=0;i<=m;i++){while(j&&s2[i]!=s2[j+1])j=ne[j];if(s2[i]==s2[j+1])j++;ne[i]=j;}for(int i=1,j=0;i<=n;i++){stk[++top]=i;while(j&&s1[i]!=s2[j+1])j=ne[j];if(s1[i]==s2[j+1])j++;pos[i]=j;if(j==m){top-=m;j=pos[stk[top]];}}for(int i=1;i<=top;i++){cout<<s1[stk[i]];}return 0;
}

用另外一个数组来模拟删除的过程，其中通过top来模拟数组的最后一位。

H - Compress Words：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1000010;
ll n,len,anslen,top,minn,kmp[maxn];
char c[maxn],ans[maxn];
int main(){ cin>>n;for(int i=1;i<=n;i++){scanf("%s",c+1);len=strlen(c+1);minn=min(anslen,len);top=len;c[++top]='#';for(int j=1;j<=minn;j++)c[++top]=ans[anslen-(minn-j)];for(int j=1;j<top;j++){ll k=kmp[j];while(k&&c[k+1]!=c[j+1])k=kmp[k];if(c[k+1]==c[j+1])k++;kmp[j+1]=k;}for(int j=kmp[top]+1;j<=len;j++)ans[++anslen]=c[j];}for(int i=1;i<=anslen;i++)cout<<ans[i];return 0;
}

I - 动物园：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
typedef long long ll;
int ne[N],ans[N];
int main(){int t;cin>>t;while(t--){ll res=1;memset(ne,0,sizeof(ne));string s;cin>>s;int n=s.size();ans[0]=0;ans[1]=1;for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=s[j])j=ne[j];if(s[i]==s[j])j++;ne[i+1]=j;ans[i+1]=ans[j]+1;	}for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=s[j])j=ne[j];if(s[i]==s[j])j++;while(2*j>(i+1))j=ne[j];res=(res*(ll)(ans[j]+1)%mod);}cout<<res<<endl;}return 0;
}