POJ1961. Period（KMP + 最小循环元）

链接：https://ac.nowcoder.com/acm/problem/50990
来源：牛客网

题目描述

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)(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 AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.

输入描述:

The input consists of several test cases. Each test case consists of two lines. The first one contains N (2≤N≤1000000)(2≤N≤1000000)– 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.

输出描述:

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.

示例1

输入

复制

3
aaa
12
aabaabaabaab
0

输出

复制

Test case #1
2 2
3 3

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

KMP求最小循环元，证明见蓝书p74.

#include <iostream>
using namespace std;
int n, nxt[1000005];
string s;
void get_nxt() {
	nxt[1] = 0;
	for(int i = 2, j =  0; i <= n; i++) {
		while(j > 0 && s[i] != s[j + 1]) j = nxt[j];
		if(s[i] == s[j + 1]) j++;
		nxt[i] = j;
	}
}
int main() {
	//freopen("data.txt", "r", stdin);
	int cnt = 0;
	while(cin >> n && n) {
		cnt++;
		cin >> s;
		s = " " + s; 
		get_nxt();
		cout << "Test case #" << cnt << endl;
		for(int i = 2; i <= n; i++) {
			if(i % (i - nxt[i]) == 0 && i / (i - nxt[i]) > 1) {
				cout << i << ' ' << i / (i -   nxt[i]) << endl;
			}
		}
		cout << endl;
	}
	return 0;
}