hdu 1358 Period(给定一个字符串,求有多少个前缀(包括自己本身),它是由k(k>2,并且尽量大)个循环节组成的)

最后更新于:2022-04-01 16:02:05

代码: ~~~ #include<cstdio> #include<cstring> using namespace std; int LCPS[1000005]; int next[1000005]; char s[1000005]; int n; void GetLCPS() { int j=0; int k=-1; next[0]=-1; while(j<n) { if(k==-1||s[k]==s[j]) { LCPS[j++]=++k; next[j]=k; } else { if(k-1>=0) k=LCPS[k-1]; else k=-1; } } } int main() { int cnt=0; while(scanf("%d",&n)&&n) { printf("Test case #%d\n",++cnt); scanf("%s",s); GetLCPS(); for(int i=1;i<n;i++) { int cir=(i+1)-(next[i+1]); int r=(i+1)%cir; int k=(i+1)/cir; if(r==0&&k>1) { printf("%d %d\n",i+1,k); } } printf("\n"); } return 0; } ~~~
';