hdu_1358Period(kmp找循环前缀)

Period

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6233 Accepted Submission(s): 3015

Problem Description

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.

Input

The 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.

Output

For 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

3 aaa 12 aabaabaabaab 0

Sample Output

Test case #1 2 2 3 3 Test case #2 2 2 6 2 9 3 12 4

题意：给出一个字符串，然你找到所有的前缀是循环串的前缀长度，和对应的循环节的循环次数

题解：

总结一下，如果对于next数组中的 i，符合 i % ( i - next[i] ) == 0 && next[i] != 0 , 则说明字符串0-n-1循环，而且

循环节长度为: i - next[i]

循环次数为: i / ( i - next[i] )

如果要问为什么可以自习用几个栗子，然后啃一啃

或者看这里：

next[i]数组的含义是0-i-1个字符中前next[i]和倒数next[i]是完全相同的，那么如果next[i] < (i-1)/2 （即如果这完全相同的前缀和后缀不重合的话）那么有i-next[i]>(i-1)/2则i不可能有i%[i-next[i]]==0这种情况是不可能有循环串的，因为如果是循环串，公共的前缀和后缀肯定是重合的

下面考虑如果重合的情况，如果重合的话，那么一定有i-next[i]就是最小的循环节长度，自己画个图仔细理解一下

然后就有了上面的结论。还是要理解好next的本质才可以

下面给出这个题的代码：

 1 /*
 2 对next的理解更深入了点儿。
 3     字符编号从0开始，那么if(i%(i-next[i])==0)，注意，还要保证循环次数大于1，则i前面的
 4 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。
 5 还要注意Next数组处理的是当前这个数的前缀，所以要处理最后一个字符就要再有面再加一位防止漏解
 6  Print a blank line after each test case.注意这个pe了一次
 7 */
 8 
 9 #include<cstdio>
10 #include<cstring>
11 #include<algorithm>
12 using namespace std;
13 const int N = 1000005;
14 char b[N];
15 int Next[N];
16 void get_next(int n)
17 {
18     for(int i = 0; i <= n; i++) Next[i]=0;
19     int tm;
20     tm = Next[0] = -1;
21     int j = 0;
22     while(j<n){
23         if(tm<0||b[j]==b[tm]) {
24             Next[++j] = ++tm;
25         }
26         else tm = Next[tm];
27     }
28     return;
29 }
30 int main()
31 {
32     int c = 1;
33     int n;
34     while(~scanf("%d",&n),n)
35     {
36         getchar();
37         scanf("%s",b);
38         b[n] = '#';
39         get_next(n);
40         printf("Test case #%d
",c++);
41         for(int i = 1; i <= n; i++){
42             int t = i - Next[i];
43             if(i%t==0&&i/t>1){
44                 printf("%d %d
",i,i/(i-Next[i]));
45             }
46         }
47         printf("
");
48     }
49     return 0;
50 }