AcWing 141. 周期 || HDU 1358 Period(KMP循环节)

#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
int len;
char s[maxn];
int Next[maxn];

void init(){
	int j = 0, k = -1;
	memset(Next, -1, sizeof(Next));
	while(j < len){
		if(k == -1 || s[j] == s[k]){
				k ++;
				j ++;
				Next[j] = k;
		}
		else k = Next[k];
	}
}

int main()
{
	int Case = 1;
	while(~scanf("%d", &len)){
		if(len == 0) break;
 		scanf("%s", s);
		init();
		printf("Test case #%d\n", Case ++);
		for(int i=2;i<=len;i++){
			int xx = i - Next[i];
			if(i != xx && i % xx == 0){
				printf("%d %d\n", i, i / xx);
			}
		}
		puts("");
	}
	return 0;
}