Coder Space

类似于2406，只是对字符串的每一前缀都要判断一次，参看2046 Power Strings。

题意：给一个字符串S长度不超过10^6，对S的每个子串str求最大的n使得str由n个相同的字符串a连接而成，如："ababab"则由n=3个"ab"连接而成，"aaaa"由n=4个"a"连接而成，"abcd"则由n=1个"abcd"连接而成。

定理：假设S的长度为len，则S存在循环子串，当且仅当，len可以被len - next[len]整除，最短循环子串为S[len - next[len]]

例子证明：
设S=q1q2q3q4q5q6q7q8，并设next[8] = 6，此时str = S[len - next[len]] = q1q2，由字符串特征向量next的定义可知，q1q2q3q4q5q6 = q3q4q5q6q7q8，
即有q1q2＝q3q4，q3q4＝q5q6，q5q6＝q7q8，即q1q2为循环子串，且易知为最短循环子串。由以上过程可知，若len可以被len - next[len]整除，则S存在循环子串，否则不存在。

解法：利用KMP算法，求字符串的特征向量next，若len可以被len - next[len]整除，则最大循环次数n为len/(len - next[len])。对字符串的每一个前缀子串都进行一次判断。

源代码
 1#include<iostream>
 2
 3using namespace std;
 4
 5const int MAXN = 1000001;
 6
 7char s[MAXN];
 8int N[MAXN];
 9
10//求字符串的特征向量
11void Next(char str[],int m)
12{
13    N[0] = 0;
14    for(int i = 1; i < m; i++)
15    {
16        int k = N[i-1];
17        while(k > 0 && str[i] != str[k])
18        {
19            k = N[k-1];
20        }
21        if(str[i] == str[k])
22        {
23            N[i] = k + 1;
24        }
25        else
26        {
27            N[i] = 0;
28        }
29    }
30}
31
32int main()
33{
34    int n;
35    int nTest = 0;
36    int t;
37
38    scanf("%d",&n);
39    while(n != 0)
40    {
41        scanf("%s",s);
42        Next(s,n);
43
44        printf("Test case #%d\n",++nTest);
45        for(int i = 2; i <= n; i++)              //判断每一个前缀子串
46        {
47            if(i % (i - N[i-1]) == 0 && (t = i/(i-N[i-1])) > 1)
48            {
49                printf("%d %d\n",i,i/(i-N[i-1]));
50            }
51        }
52        printf("\n");
53
54        scanf("%d",&n);
55    }
56    return 0;
57}
58