PRoblem Description Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n). Input Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Output For each s you should print the largest n such that s = a^n for some string a.
Example Input
abcdaaaaababab.Example Output
143Hint This problem has huge input, use scanf instead of cin to avoid time limit exceed.
Author
#include<stdio.h>#include <string.h>#define N 1010000char p[N];int main(){ while(gets(p)) { int b=strlen(p); if(b==1&&p[0]=='.')break; int max=1; int c; for(int a=1; a<=b/2;a++) { if(b%a!=0)continue; int d; for(c=0, d=0; c<b; c++, d++) { if(d==a)d=0; if(p[d]!=p[c])break; } if(c==b) { max=b/a; break; } } printf("%d/n", max); } return 0;}新聞熱點
疑難解答
