C. Sorting Substrings

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> ii;
#define S second
#define F first

vector< vector< int > > Rank;
vector< ii > Seg;
string s;
int n ,q;

void CountSort(vector< int > &SA ,vector< int > &RA ,int k ,int n)
{
    int N = max(333 ,n);
    vector< int > Cnt(N ,0);
    vector< int > tempSA(n);

    for(int i = 0 ; i < n ; i++)
        Cnt[ ( (i + k) >= n) ? 0 : RA[i + k] ] ++;

    for(int i = 0, sum = 0 ; i < N ; i++)
    {
        int t  = Cnt[i];
        Cnt[i] = sum;
        sum   += t;
    }

    for(int i = 0 ; i < n ; i++)
        tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];

    SA = tempSA;
}

void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n)
{
    CountSort(SA ,RA ,s ,n);
    CountSort(SA ,RA ,f ,n);
}

vector< vector< int > > ConstructSA(string &s ,int n)
{
    vector< vector< int > > Rank((int)log2(n) + 2 ,vector< int >(n ,0));

    vector< int > tempRA(n ,0) ,SA(n ,0);

    for(int i = 0 ; i < n ; i++) Rank[0][i] = (int)s[i];
    for(int i = 0 ; i < n ; i++) SA[i] = i;

    for(int k = 1 ; k < n ; k <<= 1 )
    {
        int LogRa = log2(k);
        RadixSort(SA ,Rank[ LogRa ] ,k ,0 ,n);

        int r = tempRA[ SA[0] ] = 0;
        for(int i = 1 ; i < n ; i++)
        {
            bool flagF = (Rank[LogRa][ SA[i] ] == Rank[LogRa][ SA[i - 1] ]);
            bool flagS = (Rank[LogRa][ ( (SA[i] + k) >= n ) ? 0 : (SA[i] + k) ] ==
                          Rank[LogRa][ ( (SA[i - 1] + k) >= n ) ? 0 : (SA[i - 1] + k) ]);

            tempRA[ SA[i] ] = (flagF && flagS) ? r : (++r);
        }

        Rank[LogRa] = tempRA;
    }

    return Rank;
}

inline int Calc(int i ,int j ,int Len ,int Log)
{
    ii a = ii( Rank[Log][i] , Rank[Log][ ( i + Len - (1 << Log) ) % n ]);
    ii b = ii( Rank[Log][j] , Rank[Log][ ( j + Len - (1 << Log) ) % n ]);
    return (a == b ? 0 : a < b ? -1 : 1);
}

inline bool Cmp(const ii &a ,const ii &b){

    int LenA = a.S - a.F + 1;
    int LenB = b.S - b.F + 1;
    int Len  = min(LenA ,LenB);
    int Log  = log2(Len);

    int Res = Calc(a.F ,b.F ,Len ,Log);

    if( Res == +1 ) return false;
    if( Res == -1 ) return true;

    if( LenA > LenB ) return false;
    if( LenA < LenB ) return true;

    return a < b;
}

int main()
{
    cin >> s >> q;

    s += ' ';
    n = s.size();
    for(int i = 0 ; i < q ; i++)
    {
        int L;  cin >> L ,L --;
        int R;  cin >> R ,R --;
        Seg.push_back( ii(L ,R) );
    }

    Rank = ConstructSA(s ,n);

    sort(Seg.begin() ,Seg.end() ,Cmp); cout << endl;

    for(auto i : Seg) cout << i.F + 1 << ' ' << i.S + 1 << endl;
}