UVA 11512 / Suffix_Array_LCP

/***
 created: 2022-05-18-17.08.41
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

struct suf
{
    ll in;
    ll rank[2];
    ll lcp;
} ;

suf suffix[1000002];

bool cmp(suf a,suf b)
{
    if(a.rank[0]==b.rank[0])
    {
        return a.rank[1]<b.rank[1];
    }

    return a.rank[0]<b.rank[0];
}

void suffixarray(string a,ll n)
{

    ll i,j,k,l;

    for(i=0; i<n; i++)
    {
        suffix[i].in=i;
        suffix[i].rank[0]=a[i]-'a';
        suffix[i].rank[1]=(i+1<n)?(a[i+1]-'a'):-1;
    }

    sort(suffix,suffix+n,cmp);

    ll index[n+2];

    for(ll k=4; k<2*n; k*=2)
    {
        ll rank = 0;
        ll p_rank=suffix[0].rank[0];
        suffix[0].rank[0]=rank;
        index[suffix[0].in]=0;

        for(i=1; i<n; i++)
        {
            if(suffix[i].rank[0]==p_rank && suffix[i].rank[1]==suffix[i-1].rank[1])
            {
                p_rank=suffix[i].rank[0];
                suffix[i].rank[0]=rank;
            }
            else
            {
                p_rank=suffix[i].rank[0];
                suffix[i].rank[0]=++rank;
            }
            index[suffix[i].in]=i;
        }
        for(i=0; i<n; i++)
        {
            ll n_ind=suffix[i].in + k/2;
            suffix[i].rank[1]=(n_ind<n)?suffix[index[n_ind]].rank[0]:-1;
        }

        sort(suffix,suffix+n,cmp);

    }
}

void lcpfind(string a,ll n)
{
    ll rank[n+4]= {0};

    ll i,j,k,l;

    for(i=0; i<n; i++)
    {
        rank[suffix[i].in]=i;
        suffix[i].lcp=0;
    }

    k=0;

    for(i=0; i<n; i++)
    {
        if(rank[i])
        {
            j=suffix[rank[i]-1].in;
            while(i+k<n && k+j<n && a[i+k]==a[k+j]) k++;

            suffix[rank[i]].lcp=k;
            if(k>0) k--;
        }
    }
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        string a;

        cin>>a;

        ll n=a.size(),mx=0,cnt=0,id,i,j,last=-1,ans=0;;

        suffixarray(a,n);

        lcpfind(a,n);

        for(i=n-1;i>=0;i--)
        {
            if(suffix[i].lcp==last) cnt++;
            else cnt=2;


            if(suffix[i].lcp && suffix[i].lcp>=mx)
            {
                mx=suffix[i].lcp;
                id=suffix[i].in;
                ans=cnt;

            }
            last=suffix[i].lcp;
        }

        if(mx==0) cout<<"No repetitions found!"<<nl;
        else
        {
            for(i=id,j=0;j<mx;i++,j++)
            {
                cout<<a[i];
            }
            cout<<" "<<ans<<nl;
        }

        // cout<<mx<<nl;
    }

    get_lost_idiot;
}