KMP习题集

添加链接描述模板题
剪花布条
AC代码

#include <bits/stdc++.h>
using namespace std;
void getNext(char p[],int Next[]){
    Next[0]=-1;
    int i=0,j=-1;
    int n=strlen(p);
    while(i<n){
        if(j==-1||p[i]==p[j]){
            i++;
            j++;
            Next[i]=j;
        }
        else
            j=Next[j];
    }
}
int KMP(char t[],char p[],int Next[]){
    int i=0,j=0;
    int n1=strlen(t);
    int n2=strlen(p);
    while(i<n1&&j<n2){
        if(j==-1||t[i]==p[j]){
            i++;
            j++;
        }
        else
            j=Next[j];
    }
    if(j==n2)
        return i;
    else
        return -1;
}
int main(){
    while(1){
        char t[1005],p[1005];
        int Next[1005];
        scanf("%s",t);
        if(t[0]=='#'){
            break;
        }
        scanf("%s",p);
        int len=strlen(t),cnt=1;
        getNext(p,Next);
        int loc=KMP(t,p,Next);
        if(loc==-1){
            printf("0\n");
            continue;
        }
        else if(loc==len){
            printf("1\n");
            continue;
        }
        else{
            while(1){
                int val=KMP(t+loc,p,Next);
                if(val==-1) break;
                loc=val+loc;
                cnt++;
            }

            printf("%d\n",cnt);
        }
    }
}

Oulipo
AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=1e6+5;
int cnt=0;
char p[10005],t[maxn];
int Next[10005];
void getNext(char p[],int Next[]){
	int i=0,j=-1;
	Next[0]=-1;
	int n=strlen(p);
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
void KMP(char t[],char p[],int Next[]){
	int i=0,j=0;
	int len1=strlen(t),len2=strlen(p);
	while(i<len1&&j<len2){
		if((j==-1||t[i]==p[j])&&j<len2-1){
			i++;
			j++;
		}
		else if(j==len2-1&&t[i]==p[j]){
			cnt++;
			j=Next[j];
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
	int num;
	scanf("%d",&num);
	while(num--){
	memset(t,'\0',sizeof(t));
	memset(p,'\0',sizeof(p));
	memset(Next,0,sizeof(Next));
	scanf("%s%s",p,t);
	cnt=0;
	getNext(p,Next);
	KMP(t,p,Next);
	printf("%d\n",cnt);
	}
	return 0;
}

Number Sequence 题解—>KMP
AC代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int p[10005],t[1000005];
int Next[10005];
void getNext(int p[],int Next[],int n){
	int i=0,j=-1;
	Next[0]=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
		//cout<<1<<endl;
	}
	return ;
}
int KMP(int t[],int p[],int Next[],int len1,int len2){
	int i=0,j=0;
	while(i<len1&&j<len2){
		if(j==-1||t[i]==p[j]){
			i++;
			j++;
		}
		else
			j=Next[j];
		//cout<<2<<endl;
	}
	if(j==len2)
	return i-j+1;
	else
	return -1;
}
int main(){
	int num;
	scanf("%d",&num);
	while(num--){
		int len1,len2;
		scanf("%d%d",&len1,&len2);
		for(int i=0;i<len1;i++){
			scanf("%d",&t[i]);
		}
		for(int i=0;i<len2;i++){
			scanf("%d",&p[i]);
		}
		getNext(p,Next,len2);
		printf("%d\n",KMP(t,p,Next,len1,len2));
	}
	return 0;
}

提升题
Simpsons’ Hidden Talents
简单评论一下：把两个字符串怎样连接成一个可以用Next解决的字符串
AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn1=5e4+5;
const int maxn=1e5+5;
char t[maxn],q[maxn];
char *p;
int Next[maxn];
void getNext(char *p,int Next[],int n){
	int i=0,j=-1;
	Next[0]=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
    while(scanf("%s%s",t,q)!=EOF){
	int len1=strlen(t);
	int len2=strlen(q);
	p=strcat(t,q);
	int mi=min(len1,len2);
	int len=len1+len2;
	getNext(p,Next,len);
	int ans=Next[len];
	while(ans>mi){
		ans=Next[ans];
	}
	if(ans==0){
		printf("0\n");
	}
	else{
		for(int i=0;i<ans;i++){
			printf("%c",t[i]);
		}
		printf(" %d\n",ans);
	}
    }
    return 0;
}

Next数组含义剖析
AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
char p[maxn];
int Next[maxn];
void getNext(char p[],int Next[],int n){
	Next[0]=-1;
	int i=0,j=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
    int n,t=0;
    while(scanf("%d",&n),n){
	t++;
	scanf("%s",p);
	getNext(p,Next,n);
	printf("Test case #%d\n",t);
	for(int i=2;i<=n;i++){
		int len=i-Next[i];
		if(i!=len&&i%len==0){
			printf("%d %d\n",i,i/len);
		}
	}
	printf("\n");
    }
    return 0;
}

比上一题水一点的题目
AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e8+5;
char p[maxn];
int Next[maxn];
void getNext(char p[],int Next[],int n){
	Next[0]=-1;
	int i=0,j=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
	while(scanf("%s",p)){
		int n=strlen(p);
		if(n==1&&p[0]=='.'){
			break;
		}
		getNext(p,Next,n);
		int len=n-Next[n];
		printf("%d\n",n%len==0?n/len:1);
	}
    return 0;
}

Next数组加强版（+回朔过程）
AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
const int mod=10007;
char p[maxn];
int Next[maxn];
void getNext(char p[],int Next[],int n){
	Next[0]=-1;
	int i=0,j=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n,ans=0;
		scanf("%d%s",&n,p);
		getNext(p,Next,n);
		for(int i=1;i<=n;i++){
			int j=i;
			while(Next[j]!=-1){
				ans++;
				if(ans>=mod)
					ans%=mod;
				j=Next[j];
			}
		}
		printf("%d\n",ans);
	}
    return 0;
}

进阶题
Cyclic Nacklace
AC代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1e5+5;
char p[maxn];
int Next[maxn];
int myabs(int x){
	return x>0?x:-x;
}
void getNext(char p[],int Next[],int n){
	Next[0]=-1;
	int i=0,j=-1;
	while(i<n){
		if(j==-1||p[i]==p[j]){
			i++;
			j++;
			Next[i]=j;
		}
		else
			j=Next[j];
	}
	return ;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%s",p);
		int n=strlen(p);
		getNext(p,Next,n);
		int len=n-Next[n];
		if(n%len==0){
			if(n!=len)
			printf("0\n");
			else
				printf("%d\n",len);
		}
		else
		printf("%d\n",len-(n-n/len*len));
	}
    return 0;
}

附上大佬题解