OJ Board

Code: Select all

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll Rank[109][200009];
struct info
{
    ll idx,tup[2];
    bool operator< (const info &a) const
    {
        if(tup[0]==a.tup[0])
            return tup[1]<a.tup[1];
        else
            return tup[0]<a.tup[0];
    }
};

info arr[200005];

void Suffix_Array(string s)
{
    ll n,i,a,b,step,jump;
    n=s.size();
    s=s+s;
    s[n+n]='\0';

    for(i=0; i<n; i++)
    {
        Rank[0][i]=s[i]-'a'+1;

        arr[i].tup[0]=0;
        arr[i].tup[1]=0;
    }

    for(step=1,jump=1; jump<=n; step++,jump=jump*2)
    {
        for(i=0; i<n; i++)
        {
            a=Rank[step-1][i];

            b=Rank[step-1][(i+jump)%n];

            arr[i].idx=i;
            arr[i].tup[0]=a;
            arr[i].tup[1]=b;
        }
        sort(arr,arr+n);

        Rank[step][arr[0].idx]=0;
        for(i=1; i<n; i++)
        {
            if(arr[i].tup[0]==arr[i-1].tup[0] && arr[i].tup[1]==arr[i-1].tup[1])
                Rank[step][arr[i].idx]=Rank[step][arr[i-1].idx];
            else
                Rank[step][arr[i].idx]=i;
        }
    }
}

int main()
{
    ll t,n,m,i,j;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>s;
        n=s.size();
        Suffix_Array(s);
        cout<<arr[0].idx+1<<endl;
    }
    return 0;
}