UVa 11512 - GATTACA Solution

#include<iostream>
#include<list>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<vector>
#include<map>
#include<set>
#include<utility>
#include<iomanip>
#include<queue>

using namespace std;

#define INF (1<<29)
#define SET(a) memset(a,-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define CLR(a) memset(a,0,sizeof(a))
#define FILL(a,v) memset(a,v,sizeof(a))
#define PB push_back
#define FOR(i,n) for(int i = 0;i<n;i++)
#define PI acos(-1.0)
#define EPS 1e-9
#define MP(a,b) make_pair(a,b)
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define LL long long
#define MX 1010
#define MOD 1000000007



struct entry {
    int fst,snd, p;
    bool operator <(const entry &b) const
        {
        if(fst==b.fst) return snd<b.snd;
        else return fst<b.fst;
        }
} L[MX];

char s[MX],T[1010];
int P[20][MX],sl,tl,stp;

void suffix_array()     //from pdf
{
    for (int i = 0; i < sl; i ++)
        /*if(s[i]>='A' && s[i]<='Z')*/
            P[0][i]=s[i]-'A';
        /*else P[0][i] = s[i] - 'a'+26;*/

    stp=1;
    for (int cnt = 1; cnt >> 1 < sl; stp ++, cnt <<= 1)
    {
        for (int i = 0; i < sl; i ++)
        {
            L[i].fst = P[stp - 1][i];
            L[i].snd = i + cnt < sl ? P[stp - 1][i + cnt] : -1;
            L[i].p = i;
        }

        sort(L, L + sl);

        for (int i = 0; i < sl; i ++)
            P[stp][L[i].p] = i > 0 && L[i].fst == L[i - 1].fst && L[i].snd == L[i - 1].snd ? P[stp][L[i - 1].p] : i;
    }
}

int lcp(int x, int y)
{
    int k, ret = 0;
    if (x == y) return sl - x;
    for (k = stp-1; k >= 0 && x < sl && y < sl; k --)
    if (P[k][x] == P[k][y])
    x += 1 << k, y += 1 << k, ret += 1 << k;
return ret;
}


int main()
{
    int t,q,ret,low,high,mid;

    bool chk;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        gets(s);
        sl=strlen(s);

        suffix_array();

        int mx=0,idx;

        for(int i=0;i<sl-1;i++)
            {
                int ret=lcp(L[i].p, L[i+1].p);
                if(ret>mx)
                {
                    mx=ret;
                    idx=i;
                }
            }

        if(!mx)
            cout<<"No repetitions found!"<<endl;
        else
        {
            int cnt=2;
            for(int i=idx+2;i<sl;i++)
                if(lcp(L[idx].p, L[i].p)==mx)
                    cnt++;

            int pos=L[idx].p;
            for(int i=0;i<mx;i++)
                cout<<s[pos++];
            cout<<" "<<cnt<<endl;
        }

    }
return 0;
}