using namespace std;
typedef long long ll;
vector<ll>pi;
void ctPre(string s)
{
ll len=s.size();
pi.resize(len+5);
pi[0]=0;
for(ll i=1;i<len;i++){
ll j=pi[i-1];
while(j>0&&s[i]!=s[j])j=pi[j-1];
if(s[i]==s[j])j++;
pi[i]=j;
}
}
int main()
{
ll t;
cin>>t;
ll n;
string s;
for(ll T=1;T<=t;T++){
cin>>n>>s;
ll len=s.size();
ctPre(s);
cout<<"Test case #"<<T<<"\n";
for(ll i=1;i<len;i++){
if(pi[i]==0)continue;
ll val=(i+1)-pi[i];
if((i+1)%val==0){
cout<<(i+1)<<" "<<(i+1)/val<<"\n";
}
}
}
return 0;
}
Code language: PHP (php)