Power Strings
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 27230 | Accepted: 11401 |
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
abcdaaaaababab.
Sample Output
143
Hint
This problem has huge input, use scanf instead of cin to avoid time limit exceed.
地址：
题意：ababab，ab重复了三次，于是输出3，abcd只有自身重复了一次，输出1.。。。。。
这么一道题做了一小天，一直在想，终于想出一个自我感觉很良好的方法，把输入的字符串复制一下，还是以a，b的形式，把b后移，每次移动j-next[j]个位子，然后把后面多出去的数改成'\0'，于是用这个方式实现了好久，最终在一个细节上以失败告终，不死心想看看别人都怎么做的，看到了一句话解释next函数， 当一个字符串以0为起始下标时，next[i]可以描述为"不为自身的最大首尾重复子串长度"。原来只会求next，却没去想它真正代表的含义是什么，这样就好想了，如果是abcabcabc的话，它的next为-1，-1，-1,0,1,2,3,4,5，可以发现，如果是有重复的子段，那么它的next一定是这种情况，如果len%（len-next[len-1]-1)==0的话，那么len/（len-next[len-1]-1)一定是要求的那个值。。。。。。。。知识没学透的代价啊。。。。。。。。
#include#include #include #include #include #include #include #include using namespace std;char B[1000100];int next[1000010];void prekmp() { next[0] = -1; int j = -1; for (int i = 1; B[i]; i++) { while (j != -1 && B[i] != B[j + 1]) j = next[j]; if (B[i] == B[j + 1]) j++; next[i] = j; } int x=strlen(B); if(x%(x-next[x-1]-1)==0)printf("%d\n",x/(x-next[x-1]-1)); else printf("1\n");}int main(){ while(scanf("%s",B)&&strcmp(B,".")) { prekmp(); } return 0;}