KMP习题集
#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;
}
附上大佬题解
查看4道真题和解析