For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK , that is A concatenated K times, for some string A. Of course, we also want to know the period K.
#include<bits/stdc++.h> using namespace std; //input #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m); #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define inf 0x3f3f3f3f #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define N 1000000+5 int nex[N]; int lenp; string p; void getnext() { lenp=p.size(); nex[0]=-1; int k=-1,j=0; while(j<lenp) { if(k==-1||p[j]==p[k]) nex[++j]=++k; else k=nex[k]; } } int main() { int n; int cas=0; while(RI(n),n) { if(!n)break; printf("Test case #%d\n",++cas); cin>>p; getnext(); rep(i,1,lenp) { if(nex[i]==0)continue; int j=i-nex[i]; if(i%j==0) { printf("%d %d\n",i,i/j); } } cout<<endl; } }
原文：https://www.cnblogs.com/bxd123/p/10674374.html
