#include<bits/stdc++.h> using namespace std; #define rg register const int N=1000000+5,M=10000+5,inf=0x3f3f3f3f,P=99999997; int l,j,cnt,nxt[N],ans[N]; char s[N]; int main(){ // freopen("in2.txt","r",stdin); while(scanf("%s",s+1)==1){ memset(nxt,0,sizeof(nxt)); l=strlen(s+1),j=cnt=0; for(int i=2;i<=l;++i){ while(j&&s[i]!=s[j+1]) j=nxt[j]; if(s[i]==s[j+1]) ++j; nxt[i]=j; } int pos=l; while(nxt[pos]) ans[++cnt]=nxt[pos],pos=nxt[pos]; for(int i=cnt;i;--i) printf("%d ",ans[i]); printf("%d\n",l); } return 0; }
（1）如果len可以被len - next[len]整除，则表明字符串S可以完全由循环节循环组成，循环周期T=len/L。
（2）如果不能，说明还需要再添加几个字母才能补全。需要补的个数是循环个数L-len%L=L-(len-L)%L=L-next[len]%L，L=len-next[len]。
#include <cstdio> #include <iostream> #include <string> #include <cstring> using namespace std; #define rg register const int N=1000000+5,M=10000+5,inf=0x3f3f3f3f,P=99999997; int T,n,l,j,nxt[N],ans[N]; char s[N]; int main(){ // freopen("in2.txt","r",stdin); scanf("%d",&T); while(scanf("%s",s+1)==1&&s[1]!=‘.‘){ memset(nxt,0,sizeof(nxt)); n=strlen(s+1),j=0; for(int i=2;i<=n;++i){ while(j&&s[j+1]!=s[i]) j=nxt[j]; if(s[i]==s[j+1]) ++j; nxt[i]=j; } l=n-nxt[n]; if(n%l) puts("1"); else printf("%d\n",n/l); } return 0; }
#include <cstdio> #include <iostream> #include <string> #include <cstring> using namespace std; #define Max(x,y) (x)>(y)?(x):(y) #define Min(x,y) (x)>(y)?(y):(x) #define ll long long #define rg register const int N=10000+5,M=10000+5,inf=0x3f3f3f3f,P=99999997; int r,c,w=0,h=0,nxt[N],ans[N]; char s[N][N]; int KMP(int pos,int flag){ memset(nxt,0,sizeof(nxt)); int j=0,l; if(!flag){ for(int i=2;i<=c;++i){ while(j&&s[pos][j+1]!=s[pos][i]) j=nxt[j]; if(s[pos][i]==s[pos][j+1]) ++j; nxt[i]=j; } return c-nxt[c]; } else{ for(int i=2;i<=r;++i){ while(j&&s[j+1][pos]!=s[i][pos]) j=nxt[j]; if(s[i][pos]==s[j+1][pos]) ++j; nxt[i]=j; } return r-nxt[r]; } } int main(){ // freopen("in2.txt","r",stdin); scanf("%d%d",&r,&c); for(int i=1;i<=r;++i) scanf("%s",s[i]+1); for(int i=1;i<=r;++i) w=Max(w,KMP(i,0)); for(int i=1;i<=c;++i) h=Max(h,KMP(i,1)); printf("%d\n",w*h); return 0; }
原文：https://www.cnblogs.com/lxyyyy/p/11253164.html