For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as A K , that is A concatenated K times, for some string A. Of course, we also want to know the period K.
InputThe input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it. OutputFor each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case. Sample Input
3aaa12aabaabaabaab0Sample Output
Test case #12 23 3Test case #22 26 29 312 4 题目意思是找出字符串中由两个或以上相同的子字符串组成的前缀，输出前缀长度及其中相同的子字符串的个数。比如说aabaabaabaab,前缀aa由俩a组成，前缀aabaab由俩aab组成，都满足啦。对于长度为i的前缀串，需要找出它的相等的前后缀，如果相等的前后缀之间没有多余字符，也就是说要么是aabaab这种最大前后缀是aab，或者是aabaabaab这种最大前后缀是aabaab，相同前后缀长度不低于总串长度i的一半，才有可能满足，例如这种abcab相同前后缀是ab,肯定不满足了。对于可能满足的，要用这个前缀的长度i减去他的最大前后缀长度得到非重叠部分的长度，如果i是这个长度的倍数，且不止一倍，就是满足了。 先确立Next数组，记录最长相同的前后缀长度。然后排着去判断[1,n]长度的前缀是否满足。 代码：
#include#include #include char str[1000000];int Next[1000000],n,k;void findNext() { int j = -1,i = 0; Next[0] = -1; while(i < n) { if(j == -1 || str[i] == str[j]) { Next[++ i] = ++ j; } else j = Next[j]; }}int main() { while(~scanf("%d",&n) && n) { scanf("%s",str); findNext();///先确立Next数组 printf("Test case #%d\n",++ k); for(int i = 1;i <= n;i ++) { if(!Next[i]) continue;///没有相同前后缀 直接过 int j = i - Next[i]; if(i % j == 0) printf("%d %d\n",i,i / j); } puts(""); }}