记录编号	559205	评测结果	AAAAAAA
题目名称	3430.字符串周期（Period）	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2021-02-20 15:29:47	内存使用	1.93 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
int next[maxn];
char s[maxn];
int n;
void GetNext(char* s) {
	int i = 2,j = 0;
	next[1] = 0;
	for(;i <= n;++ i) {
		while(j&&s[i] != s[j + 1])j = next[j];
		if(s[i] == s[j + 1])++ j;
		next[i] = j;
	}
} 
int main() {
	freopen("strperiod.in","r",stdin);
	freopen("strperiod.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s + 1);
	GetNext(s);                  
	for(int i = 2;i <= n;++ i) {
		if(i % (i - next[i]) == 0&&i / (i - next[i]) > 1) {
			printf("%d %d\n",i,i / (i - next[i]));
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}