PERIOD SPOJ

#include<stdio.h>
#include<iostream>
using namespace std;
void KMP_MATCHER(string,int);
void Compute_prefix(int [],string ,int);
int main(void)
{
    int T,n,i=1;
    string P;
    scanf("%d",&T);
    while(T--)
    {
        cin>>n>>P;
        printf("Test case #%d\n",i);
        i++;
        KMP_MATCHER(P,n);
        printf("\n");
    }
        return 0;
}
void KMP_MATCHER(string P,int z)
{
    int q,i,n,m;
    m=z;
    int PHI[m];
    Compute_prefix(PHI,P,m);
 //   for(i=1;i<=m;i++) printf("%d ",PHI[i]);
    for(i=2;i<=m;i++)
        if(i%(i-PHI[i])==0)
        {
            n=i/(i-PHI[i]);
            if(n!=1)
            printf("%d %d\n",i,n);
        }
    return;
}
void Compute_prefix(int PHI[],string P,int m)
{
    PHI[0]=0;
    PHI[1]=0;
    int q,k=0;
    for(q=2;q<=m;q++)
    {
        while(k>0&&P.at(k)!=P.at(q-1))
            k=PHI[k];
        if(P.at(k)==P.at(q-1))
            k=k+1;
        PHI[q]=k;
    }
    return;
}