1 /*
2 前缀子串能否有某个周期串重复k次,输出子串长度和最大的k,也就是最小周期情况下的k。
3 也就是说求前缀子串的最大循环节
4 方法: 遍历前缀子串,若周期存在则输出,关键在于如何求最小周期
5 */
6 #include <iostream>
7 #include <cstdlib>
8 #include <cstring>
9 #include <string>
10 using namespace std;
11 int next[1000010];
12 string s;
13 void get()
14 {
15 int i=0,j=-1,k;
16 memset(next,0,sizeof(next));
17 next[0] = -1;
18 while(i<s.length())
19 {
20 if(j==-1||s[i]==s[j])
21 {
22 i++;
23 j++;
24 next[i] = j;
25 }
26 else
27 j = next[j];
28 }
29 }
30 int main()
31 {
32 int i,j,k,t;
33 int T;
34 int flag = 1;
35 while(cin>>T,T)
36 {
37 int f = 1;
38 s.clear();
39 cin>>s;
40 get();
41 cout<<"Test case #"<<flag<<endl;
42 for(i=2;i<=s.length();i++)
43 {
44 int temp = i - next[i];
45 if(i%temp==0&&i!=temp)//若不加上 i!=temp,第二组会多输出3 1
46 {
47 int ans = i/temp;
48 cout<<i<<" "<<ans<<endl;
49 }
50 }
51 flag ++;
52 cout<<endl;
53 }
54 return 0;
55 }
56
57
58 超时