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