Period

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


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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 str a a b a a b a a b a a b \0
next[i] -1 0 1 0 1 2 3 4 5 6 7 8 9


GetNext函數的時候可以取得12的next值。i為11時，比較不相等，返回到8，意味著在11的時候，比較不相等，跳轉至8的位置。為什麼跳轉到8呢？因為之前的都相等，而8和11位置處的關系不確定，所以跳至8的位置。當然，可以優化GetNext算法。

//============================================================================
// Name        : KMP_hdu1358.cpp
// Author      : vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include 
#include 
#include 

using namespace std;

int i, j, m ,n;
char str[1000001];
int next[1000001];
int ch;
int no;

void GetNext() {
	j = 0;
	i = -1;
	next[0] = -1;
	while (j < n) {
		if (i == -1 || str[i] == str[j]) {
			i++, j++;
			next[j] = i;
		} else {
			i = next[i];
		}
	}
}

int main() {
	no = 1;
	while(cin >> n){
		if(n == 0)
			break;
		scanf("%s", str);
		GetNext();
		printf("Test case #%d\n", no);
		no++;
		for(i = 2; i <= n; i++){
			ch = i - next[i];
			if(i % ch == 0){//可以想成（i - 1） - 0 + 1
				if(i / ch > 1){//重復次數大於1
					printf("%d %d\n",i,i / ch);
				}
			}
		}
		printf("\n");
	}
	return 0;
}

//優化的算法

void GetNextval(){//用此算法生成的nextval數組，不能用上面的算法進行計算。原因很簡單：把相同的串重復跳轉判斷的部分放在了nextval生成裡面，所以減少KMP的比較次數的同時，也造成了無法找到重復串的次數。
	j = 0;
	i = -1;
	nextval[0] = -1;
	while(j < n){
		if(i == -1 || str[i] == str[j]){
			i++, j++;
			if(str[i] == str[j])
				nextval[j] = i;
			else
				nextval[j] = nextval[i];
		} else
			i = nextval[i];
	}
}