这题同hdu3746一样,都是通过KMP找到字符串的最小循环节。这题wa了一次,刚开始以为一定有len%(len-next[len-1])==0,后来证实是错的。如:ababa,按照之前的做法输出2,很显然n=1。
#include<stdio.h> #include<string.h> #define N 1000005 char s[N]; int next[N],len; void getnext() { int i,j; next[0]=0; for(i=1,j=0;s[i];i++) { while(j>0&&s[i]!=s[j]) j=next[j-1]; if(s[i]==s[j]) j++; next[i]=j; } len=i; } int main() { while(~scanf("%s",s)) { if(strcmp(s,".")==0) break; getnext(); if(len%(len-next[len-1])==0) printf("%d\n",len/(len-next[len-1])); else printf("1\n"); } return 0; }