Analysis
结论：设字符串长度为n，最长相同前后缀的长度为kmp[i]，如n%(n-kmp[n])=0，则答案为n/(n-kmp[n])，否则为1。
如果循环节多于一个，以前n-kmp[n]个为循环节，是可以铺满整串的。而且因为kmp[n]是尽量大的，所以这样得到的循环节长度为所有可能情况中最小的，也就是我们所求的。
而如果n%(n-kmp[n])≠0，可以认为之前的循环节匹配仍然可以进行，但是最后一个循环节被强行割掉了一些。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1000010 6 using namespace std; 7 inline void write(int x) 8 { 9 if(x<0){putchar('-');x=-x;} 10 if(x>9)write(x/10); 11 putchar(x%10+'0'); 12 } 13 char a[maxn]; 14 int n,i,j,kmp[maxn]; 15 int main() 16 { 17 while(1) 18 { 19 cin>>a+1; 20 n=strlen(a+1); 21 if(a[1]=='.'&&n==1)break; 22 j=0; 23 kmp[1]=0; 24 for(int i=2;i<=n;i++) 25 { 26 while(j>0&&a[i]!=a[j+1])j=kmp[j]; 27 if(a[i]==a[j+1])j++; 28 kmp[i]=j; 29 } 30 if(n%(n-kmp[n])==0) 31 { 32 write(n/(n-kmp[n])); 33 printf(" "); 34 } 35 else 36 { 37 write(1); 38 printf(" "); 39 } 40 } 41 return 0; 42 }
请各位大佬斧正（反正我不认识斧正是什么意思）