Period

3
aaa
12
aabaabaabaab
0

Test case #1
2 2
3 3

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

也是一个KMP求周期的题目

与之前类似

不知道为啥next开成全局的就CE了，难道全局的就会和stl里的函数冲突。。

。

AC代码：

#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int n;
char s[1000005];

int s_next[1000005];

int main() {
	int cas = 1;
	while(scanf("%d", &n) != EOF) {
		if(n == 0) break;
		
		memset(s_next, 0, sizeof(s_next));
		s_next[0] = -1;
		scanf("%s", s);
		int i = 0, j = -1;
		while(i < n) {
			if(j == -1 || s[i] == s[j]) s_next[++ i] = ++ j;
			else j = s_next[j];
		}
		
		printf("Test case #%d\n", cas ++);
		
		for(int i = 2; i <= n; i ++) {
			int t = i - s_next[i];
			if(i % t == 0 && i / t > 1) {
				printf("%d %d\n", i, i / t);
			}
		}
		printf("\n");
	}
	return 0;
}