C++14(g++5.4) 解法, 执行用时: 51ms, 内存消耗: 8276K, 提交时间: 2020-06-06 10:19:36

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char str[N];
int net[N],n;
void get_next()
{
	
	for(int i=2,j=0;i<=n;i++)
	{
	   while(j>0&&str[i]!=str[j+1])j=net[j];
	   if(str[i]==str[j+1])j++;
	   net[i]=j;
	}
}
int main()
{
	int T=0;
	while(scanf("%d",&n),n)
	{
		scanf("%s",str+1);
		get_next();
		printf("Test case #%d\n",++T);
		for(int i=2;i<=n;i++)
		{
			int t=i-net[i];
			if(i!=t&&i%t==0)printf("%d %d\n",i,i/t);
		}
		puts("");
	}
 }

C++(g++ 7.5.0) 解法, 执行用时: 43ms, 内存消耗: 10272K, 提交时间: 2023-07-27 10:02:36

#include<bits/stdc++.h>
using namespace std;
char a[1000001];
long long nex[1000001],n,t;
inline void calc_next(){
	nex[1]=0;
	for(register int i=2,j=0;i<=n;++i){
		while(j&&a[i]!=a[j+1])j=nex[j];
		if(a[i]==a[j+1])++j;
		nex[i]=j;
	}
}
int main(){
	while(scanf("%lld",&n)&&n){
		scanf("%s",a+1);calc_next();printf("Test case #%d\n",++t);
		for(register int i=2;i<=n;++i)if(i%(i-nex[i])==0&&i/(i-nex[i])>1)printf("%lld %lld\n",i,i/(i-nex[i]));
		puts("");
	}
}

C++(clang++ 11.0.1) 解法, 执行用时: 39ms, 内存消耗: 6356K, 提交时间: 2023-03-19 08:28:13

#include<iostream>
using namespace std;
char s[10000000];
int n,ne[10000000],T=1;
int main()
{
    while(cin>>n,n)
    {
		scanf("%s",s+1);
		for(int i=2,j=0;i<=n;i++)
		{
			while(j>0&&s[i]!=s[j+1])j=ne[j];
			if(s[i]==s[j+1])j++;
			ne[i]=j;
		}
		printf("Test case #%d\n",T++);
		for(int i=1;i<=n;i++)
		{
			int t=i-ne[i];
			if(i%t==0&&i/t>1)
				printf("%d %d\n",i,i/t);
		}
		puts("");
	}
}