Suffix Array

#define mx 1005
#define ll long long int
struct suff
{
    int index;
    int Rank[2];
    bool operator <(const suff &o)const{
        return (Rank[0]<o.Rank[0])||(Rank[0]==o.Rank[0]&&Rank[1]<o.Rank[1]);
    }
};

suff suffix[mx];ll lcp[mx];suff tmp[mx];int n,fr[mx];string s;int ind[mx],sa[mx];
char str[mx];int R[mx];

void Sort(int u)
{
    int maxi=max(n,256);
    memset(fr,0,sizeof(fr));
    for(int i=0;i<n;i++)fr[suffix[i].Rank[u]+1]++;
    ll sum=0;
    for(int i=0;i<=maxi;i++)
    {
        ll prev=fr[i];
        fr[i]=sum;
        sum+=prev;
    }
    for(int i=0;i<n;i++)
    {
        tmp[fr[suffix[i].Rank[u]+1]]=suffix[i];
        fr[suffix[i].Rank[u]+1]++;

    }
    for(int i=0;i<n;i++)suffix[i]=tmp[i];
}

void SA()
{
    int mini=10000;
    for(int i=0;i<n;i++)
    {
        mini=min(mini,(int)s[i]);
    }
    for(int i=0;i<n;i++)
    {
        suffix[i].index=i;
        suffix[i].Rank[0]=s[i]-mini;
        if(i+1<n)suffix[i].Rank[1]=s[i+1]-mini;
        else suffix[i].Rank[1]=-1;
    }
    Sort(1);Sort(0);
    for(int k=4;k<2*n;k=k*2){
        int r=0;
        ind[suffix[0].index]=0;
        int prev=suffix[0].Rank[0];
        suffix[0].Rank[0]=r;
        for(int i=1;i<n;i++){
            if(prev==suffix[i].Rank[0]&&suffix[i].Rank[1]==suffix[i-1].Rank[1])
            {

                prev=suffix[i].Rank[0];
                suffix[i].Rank[0]=r;
            }
            else{
                prev=suffix[i].Rank[0];
                suffix[i].Rank[0]=++r;
            }
            ind[suffix[i].index]=i;
        }
        for(int i=0;i<n;i++){
            int next=suffix[i].index+k/2;
            if(next<n)suffix[i].Rank[1]=suffix[ind[next]].Rank[0];
            else suffix[i].Rank[1]=-1;
        }
        Sort(1);Sort(0);
    }

    //for(int i=0;i<n;i++)cout<<suffix[i].index<<endl;
}

void kasai()
{
    int k=0;ll gum=0;
    for(int i=0;i<n;i++)R[suffix[i].index]=i;
    for(int i=0;i<n;i++)sa[R[i]]=i;
    for(int i=0;i<n;i++)
    {
        if(R[i]==n-1)
        {
            k=0;
            continue;
        }
        int j=suffix[R[i]+1].index;
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        lcp[R[i]]=k;
        if(k>0)k--;
    }


}

int main()
{

        int t;
        scanf("%d",&t);
        while(t--){
        scanf("%s",str);
        s=str;
        n=s.length();
        SA();
        kasai();
        ll ans=0;

        //for(int i=0;i<n-1;i++)cout<<lcp[i]<<endl;
        ll maxi=0,save=-1;int mnt=1,save2=1;
        for(int i=0;i<n-1;i++)
        {
            if(lcp[i]>maxi)
            {
                maxi=lcp[i];
                save=sa[i];
            }
        }
        if(maxi==0)printf("No repetitions found!\n");
        else
        {
            int cnt=save;
            for(int i=0;i<maxi;i++)printf("%c",s[cnt++]);
            for(int i=0;i<n;i++)
            {
                if(sa[i]==save)
                {
                    while(lcp[i]==maxi)
                    {
                        save2++;
                        i++;
                        if(i==n-1)break;
                    }
                    break;
                }
            }
            printf(" %d\n",save2);
        }
    }



    return 0;
}