SPOJ – PERIOD – Period

#include<bits/stdc++.h>
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)