2021.08.30 前缀函数和KMP
2021/9/1 23:36:17
本文主要是介绍2021.08.30 前缀函数和KMP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
2021.08.30 前缀函数和KMP
KMP算法详解-彻底清楚了(转载+部分原创) - sofu6 - 博客园 (cnblogs.com)
KMP算法next数组的一种理解思路 - 挠到头秃 - 博客园 (cnblogs.com)
练习题
求next典范代表
UVA455 周期串 Periodic Strings - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100;
int t,nexti[N];
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
//freopen("1.out","w",stdout);
t=read();
while(t--){
scanf("%s",s);
int j=0,k=-1;
nexti[0]=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k])nexti[++j]=++k;
else k=nexti[k];
}
//for(int i=0;i<=strlen(s);i++)cout<<next[i]<<" ";
if(!(strlen(s)%(strlen(s)-nexti[strlen(s)])))
cout<<strlen(s)-nexti[strlen(s)];
else cout<<strlen(s);
//cout<<strlen(s)-nexti[strlen(s)];
if(t)cout<<endl<<endl;
else cout<<endl;
}
return 0;
}
UVA11452 Dancing the Cheeky-Cheeky - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2010;
int t,nexti[N];
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
//freopen("uva11452.out","w",stdout);
t=read();
while(t--){
scanf("%s",s);
memset(nexti,0,sizeof(nexti));
nexti[0]=-1;
int j=0,k=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k])nexti[++j]=++k;
else k=nexti[k];
}
//for(int i=0;i<=strlen(s);i++)cout<<nexti[i]<<" ";cout<<endl;
int n=strlen(s)-nexti[strlen(s)],start=nexti[strlen(s)];
start%=n;
//while(start>n)start=nexti[start];
//cout<<start<<endl;
for(int i=start;i<start+8;i++)cout<<s[i%n];cout<<"...";
cout<<endl;
}
return 0;
}
UVA10298 Power Strings - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
注：一下3种写法都没有问题，原来都是读入的锅！！！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,nexti[N];
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
//freopen("uva10298.out","w",stdout);
while(1){
scanf("%s",s);
if(strlen(s)==1&&s[0]=='.')return 0;
//memset(nexti,0,sizeof(nexti));
nexti[0]=-1;
int j=0,k=-1;
/*while(j<strlen(s)){
if(k==-1||s[j]==s[k])++j,++k,nexti[j]=k;
else k=nexti[k];
}*/
for(;j<strlen(s);j++){
while(k!=-1&&s[j]!=s[k])k=nexti[k];
++k;
nexti[j+1]=k;
}
/*for(int i=0;i<strlen(s);i++){
while(s[i+1]!=s[k+1]&&k!=-1)k=nexti[k];
if(s[i+1]==s[k+1])nexti[i+1]=++k;
}*/
//错误写法，懒得改了
//for(int i=0;i<=strlen(s);i++)cout<<nexti[i]<<" ";cout<<endl;
int n=strlen(s)-nexti[strlen(s)];
if(strlen(s)%n==0)cout<<strlen(s)/n<<endl;
else cout<<"1"<<endl;
}
return 0;
}
[P4391 BOI2009]Radio Transmission 无线传输 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
会TLE最后一个点的写法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,nexti[N];
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void getnext(char s[]){
int j=0,k=-1;nexti[0]=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k]){
//cout<<j<<" "<<k<<endl;
if(s[++j]==s[++k])nexti[j]=nexti[k];//,cout<<j<<" "<<k<<endl<<endl;
//这一步实际上是从主串的角度考虑
//如果主串和模式串在i、j比较得了，在i+1、j+1比较不了
//那么模式串应该转跳为nexti[j+1]
//因为是前0~j和前i-j+1~i比较得了，继续转跳nexti[nexti[j+1]]
//反正都要转跳至少两次，那就直接让nexti[j]==nexti[k]好了(这里指++j和++k)
else nexti[j]=k;
//如果在++j和++k处就不想等，直接转跳就对了
}
else k=nexti[k];
//如果在k和j处不相等，说明在0~k-1和j-k+1~j-1处相等，转跳nexti[k]
}
}
int main(){
n=read();
scanf("%s",s);
getnext(s);
//cout<<" Case 1"<<endl;
for(int i=0;i<=n;i++)cout<<nexti[i]<<" ";cout<<endl;
cout<<strlen(s)-nexti[strlen(s)];
return 0;
}
学会的新写法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,nexti[N];
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
int main(){
n=read();
scanf("%s",s+1);
int j=0;
for(int i=1;i<=n;i++){
while(s[i+1]!=s[j+1]&&j)j=nexti[j];
if(s[i+1]==s[j+1])nexti[i+1]=++j;
}
//for(int i=1;i<=n+1;i++)cout<<nexti[i]<<" ";cout<<endl;
cout<<n-nexti[n];
return 0;
}
CF126B Password - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
论我把Just a legend拼为Judge a legent并且第二次该还改错为Just a legent的悲剧故事
//找到这道即使kmp的nexti数组就能求出来的，又是exkmp能求出来
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int nexti[N];
char s[N];
int main(){
scanf("%s",s);
int j=0,k=-1;
nexti[0]=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k])nexti[++j]=++k;
else k=nexti[k];
}
int maxn=0;
//for(int i=0;i<=strlen(s);i++)cout<<nexti[i]<<" ";cout<<endl;
for(int i=2;i<strlen(s);i++)maxn=max(maxn,nexti[i]);//,cout<<nexti[i]<<" ";
//cout<<endl;
//cout<<maxn<<endl;
k=nexti[strlen(s)];
while(k>maxn)k=nexti[k];
if(k)for(int i=0;i<k;i++)cout<<s[i];
else cout<<"Just a legent";
return 0;
}
[P2375 NOI2014] 动物园 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
MD,为啥总是TLE？！为啥开了O2优化还多TLE了一个？
我的60分代码：
//论当我看到第三个样例却怎么也算不出结果结果发现是看错题的绝望！！
//论nexti数组的神奇应用
//nexti数组本来就是求出0~i为最大的前缀后缀重复的长度
//那么nexti[nexti[i]]也是i的重复前缀后缀
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
typedef long long ll;
int n,nexti[N];
ll num[N],ans;
char s[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
/*void getnext(char s[]){
int j=0,k=-1;nexti[0]=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k])nexti[++j]=++k;
else k=nexti[k];
num[j]=num[k]+1;
}
}*/
void getnext(char s[]){
int j=0;
for(int i=1;i<strlen(s);i++){
while(j&&s[i]!=s[j])j=nexti[j];
if(s[j]==s[i])++j;
nexti[i+1]=j;
num[i+1]=num[j]+1;
}
}
int main(){
n=read();
while(n--){
scanf("%s",s);
memset(nexti,0,sizeof(nexti));
num[0]=0;
num[1]=1;
getnext(s);
ans=1;
int j=0;
for(int i=1;i<strlen(s);i++){
while(s[j]!=s[i]&&j)j=nexti[j];
if(s[i]==s[j])++j;
while((j<<1) > i+1)j=nexti[j];
ans=(ans*(num[j]+1)%mod)%mod;
}
cout<<ans<<endl;
}
return 0;
}
真正的kmp
UVA12604 Caesar Cipher - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
别人的满分代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=500003;
int pos[130],nxt[maxn],ans[maxn],cnt;
char a[maxn],b[maxn],c[maxn],noww[maxn];
void getnext(char t[])
{
int i=0,j=-1,lent=strlen(t); nxt[0]=-1;
while(i<lent)
{
if(j==-1||t[i]==t[j]) nxt[++i]=++j;
else j=nxt[j];
}
}
int kmp(char s[],char t[])
{
int i=0,j=0,ans=0,lens=strlen(s),lent=strlen(t);
while(i<lens)
{
if(j==-1||s[i]==t[j]) ++i,++j;
else j=nxt[j];
if(j==lent) ++ans,j=nxt[j];
}
return ans;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
cnt=0;
scanf("%s%s%s",&a,&b,&c);
int lena=strlen(a),lenb=strlen(b),lenc=strlen(c);
for(int i=0;i<lena;++i) pos[a[i]]=i;
for(int i=0;i<lena;++i)
{
for(int j=0;j<lenb;++j) noww[j]=a[(pos[b[j]]+i)%lena];
noww[lenb]='\0';
getnext(noww);
if(kmp(c,noww)==1) ans[++cnt]=i;
}
if(!cnt)cout<<"no solution"<<endl;
else if(cnt==1) cout<<"unique: "<<ans[1]<<endl;
else
{
cout<<"ambiguous:";
for(int i=1;i<=cnt;++i) cout<<" "<<ans[i];
cout<<endl;
}
}
return 0;
}
我的一直waiting的代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=5e5+10;
int t,mapi[130],nexti[N],ans[N],cnt;
char a[N],b[N],c[N],now[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void getnext(char s[]){
int j=0,k=-1;nexti[0]=-1;
while(j<strlen(s)){
if(k==-1||s[j]==s[k])nexti[++j]=++k;
else k=nexti[k];
}
}
int kmp(char s[],char t[]){
int i=0,j=0,ans=0;
while(i<strlen(s)){
if(j==-1||s[i]==t[j])++i,++j;
else j=nexti[j];
if(j==strlen(t))++ans,j=nexti[j];
}
return ans;
}
int main(){
//freopen("uva12604.out","w",stdout);
t=read();
while(t--){
cnt=0;
scanf("%s%s%s",a,b,c);
for(int i=0;i<strlen(a);i++)mapi[a[i]]=i;
for(int i=0;i<strlen(a);i++){
for(int j=0;j<strlen(b);j++)
now[j]=a[(mapi[b[j]]+i)%strlen(a)];
now[strlen(b)]='\0';
getnext(now);
if(kmp(c,now)==1)ans[++cnt]=i;
}
if(!cnt)cout<<"no solution"<<endl;
else if(cnt==1)cout<<"unique: "<<ans[1]<<endl;
else{
cout<<"ambiguous:";
for(int i=1;i<=cnt;i++)cout<<" "<<ans[i];
cout<<endl;
}
}
return 0;
}
UVA12467 Secret Word - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
又是神奇的错误。
别人满分代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000003;
char s[maxn],t[maxn];
int len,nxt[maxn];
void getnext(char t[])
{
int i=0,j=-1,lent=strlen(t); nxt[0]=-1;
while(i<lent)
{
if(j==-1||t[i]==t[j]) nxt[++i]=++j;
else j=nxt[j];
}
}
int kmp(char s[],char t[])
{
int i=0,j=0,ans=0,lens=strlen(s),lent=strlen(t);
while(i<lens)
{
if(j==-1||s[i]==t[j]) ++i,++j;
else j=nxt[j];
ans=max(ans,j);
if(j==lent) j=nxt[j];
}
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%s",s); len=strlen(s);
for(int i=0;i<len;++i) t[i]=s[i];
t[len]='\0';
reverse(t,t+len);
getnext(s);
for(int i=kmp(t,s)-1;i>=0;--i) cout<<s[i];
puts("");
}
return 0;
}
MD，老子改到炸也没改出来的的垃圾代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
int ti,nexti[N];
char s[N],t[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void getnext(char ch[]){
int j=0,k=-1;
nexti[0]=-1;
while(j<strlen(ch)){
if(k==-1||ch[j]==ch[k])nexti[++j]=++k;
else k=nexti[k];
}
}
/*
int kmp(char a[],char b[]){
int i=0,j=0,ans=0;
while(i<strlen(a)){
if(j==-1||a[i]==b[j])++i,++j;
else j=nexti[j];
ans=max(ans,j);
if(j==strlen(b))j=nexti[j];
ans=max(ans,j);
}
return ans;
}
*/
/*
void getnext(char t[])
{
int i=0,j=-1,lent=strlen(t); nexti[0]=-1;
while(i<lent)
{
if(j==-1||t[i]==t[j]) nexti[++i]=++j;
else j=nexti[j];
}
}
*/
int kmp(char s[],char t[])
{
int i=0,j=0,ans=0,lens=strlen(s),lent=strlen(t);
while(i<lens)
{
if(j==-1||s[i]==t[j]) ++i,++j;
else j=nexti[j];
ans=max(ans,j);
if(j==lent) j=nexti[j];
}
return ans;
}
int main(){
ti=read();
while(ti--){
scanf("%s",s);
//memcpy(t,s,sizeof(s));
for(int i=0;i<strlen(s);i++)t[i]=s[i];
t[strlen(s)]='\0';
reverse(t,t+strlen(s));
//cout<<s<<endl<<t<<endl;
memset(nexti,0,sizeof(nexti));
getnext(s);
//for(int i=0;i<=strlen(t);i++)cout<<nexti[i]<<" ";cout<<endl<<endl;
int maxn=kmp(t,s);
//cout<<"maxn "<<maxn<<endl;
for(int i=maxn-1;i>=0;i--)printf("%c",s[i]);
cout<<endl;
}
return 0;
}
exkmp
UVA11475 Extend to Palindrome - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
答案正确，却TLE的我的代码：
//exkmp的初始题~
//明白exkmp的愉悦~
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+10;
int z[N];
char s[N],s1[N/2],s2[N/2];
void getz(char s[]){
for(int i=1,l=0,r=0;i<strlen(s);i++){
if(i<=r&&z[i-l]<r-i+1)z[i]=z[i-l];
else{
z[i]=max(0,r-i+1);
while(i+z[i]<strlen(s)&&s[z[i]]==s[i+z[i]])++z[i];
}
if(i+z[i]-1>r)r=i+z[i]-1,l=i;
}
}
int main(){
//freopen("uva11475.out","w",stdout);
while(cin>>s1){
memset(z,0,sizeof(z));
int len=strlen(s1);
memcpy(s2,s1,sizeof(s1));
reverse(s2,s2+len);
//cout<<s1<<endl<<s2;
memcpy(s,s2,sizeof(s2));
s[strlen(s2)]='*';
strcat(s,s1);
//cout<<endl<<s<<endl;
getz(s);
//for(int i=0;i<strlen(s);i++)cout<<z[i]<<" ";cout<<endl;
int maxn=0,pos=0;
for(int i=strlen(s2);i<strlen(s);i++)
if(z[i]>=maxn&&i+z[i]==strlen(s))pos=i,maxn=z[i];
//cout<<maxn<<" "<<pos<<endl;
cout<<s1;
for(int i=z[pos];i<strlen(s2);i++)printf("%c",s[i]);
puts("");
}
return 0;
}
别人的不会TLE的代码，主要是前面的新写法：
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a*10)+(ch-'0');
a*=w;
}
const int MAX = 2e5+10;
template <typename T> inline void ckmax(T &a,T b){a = a>b ? a:b;}
template <typename T> inline void ckmin(T &a,T b){a = a<b ? a:b;}
int z[MAX];
inline void getZ(string s){
for(int i = 1, l = 0 , r=0 ; i < s.size(); ++i){ //exKMP的一个注意，若这里从0起，r就会等于size,就退化为n^2了
if(i <= r) z[i] = min(r-i+1,z[i-l]);
while(i+z[i] < s.size() && s[z[i]] == s[i+z[i]]) ++z[i];
if(i+z[i] - 1 > r) r=i+z[i]-1,l = i;
}
}
int main(){
string s;
while(cin >> s){
int len = s.size();
memset(z,0,sizeof(z));
string ss = s;
string t;
for(int i = 0 ; i < s.size()/2; ++i) swap(s[i] , s[len-1-i]); //翻转
t=s+"*"+ss;
getZ(t);
int ans = 0 , pos=0;
for(int i = s.size()+1; i < t.size(); ++i){
if(z[i] >= ans && i + z[i] == t.size()) pos = i, ans = z[i]; //求可删
}
cout<<ss;
/*int flag=0;
if(ss[len-1] == t[z[pos]]) flag=1;*/
for(int i = z[pos]; i < s.size(); ++i){
// if(flag && i == z[pos]) continue;
cout<<t[i];
}
puts("");
}
}
这篇关于2021.08.30 前缀函数和KMP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-26结对编程到底难不难？答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图，怎么办？
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡？
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
