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("");
}
}