Strings
Time Limit: 3000MSMemory Limit: 65536K Total Submissions: 35168Accepted: 14543 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. Sample Input
abcd aaaa ababab . Sample Output
1 4 3 Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed. Source
Waterloo local 2002.07.01
kmp求循环节。
如上图所示，红色的串的尾部就是next[l]，他和绿色的串分别代表字符串的前缀和后缀，他们是完全相同的（根据next[i]）的定义。
那么蓝色和紫色部分（长度都是）就是相同的。 因为他们分别是绿串和红串的尾部。
紫色和金色（等长）的部分也是相同的。 因为紫色部分是绿串从右往左数的第个。
两个三角部分是相同的。 因为他们分别是绿串和红串的前缀且长度相同。
接下来分情况讨论： ①三角部分的长度等于即，，循环节个数为
②三角部分的长度小于即，说明该串内部没有循环节，本身是循环节，循环节个数为1。
;char s[1000005];int ne[1000005];int main(){while (scanf(“%s”,s+1)){if (s[1]==’.’) break;int j=0;int l=strlen(s+1);for (int i=2;i<=l;i++){while (j&&s[i]!=s[j+1]) j=ne[j];if (s[i]==s[j+1]) j++;ne[i]=j;}if (l%(l-ne[l])==0) printf(“%d\n”,l/(l-ne[l]));else puts(“1”);}return 0;}附：kmp学习好文
以一种进取的和明智的方式同它们奋斗。
