Suffix Array template

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

string s;
int n;

string Read(){
    const int MaxN = 4e5 + 5e2;
    static char Buff[MaxN];
    scanf("\n%s" ,Buff);
    return Buff;
}

inline string SubStr(string &Str ,int Start ,int Len = 1e9){
    /// --- Give String + StartIdx (If You Want To The End Of String) --- ///
    /// --- Give String + StartIdx + Len (If You Want Len Of SubStr) ---- ///

    string Res;

    int N = (int)Str.size();
    Len   = max(0 ,Len);
    Start = max(0 ,Start);

    for(int i = Start ; (i < N && i < Start + Len) ; i++)
        Res += Str[i];
    return Res;
}

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

    /// --- Count The Repetitions --- ///
    for(int i = 0 ; i < n ; i++)
        Cnt[ (i + k >= n) ? 0 : RA[i + k] ] ++;

    /// --- Find The Correct Index Of Each Repetition --- ///
    for(int i = 0, sum = 0 ; i < N ; i++){
        int t = Cnt[i];
        Cnt[i] = sum;
        sum += t;
    }

    /// --- Put Each Repetition In It's Right Place --- ///
    for(int i = 0 ; i < n ; i++)
        tempSA[ Cnt[ ((SA[i] + k) < n) ? RA[ SA[i] + k ] : 0] ++ ] = SA[i];

    /// --- UPD Suffix Array --- ///
    SA = tempSA;
}

void RadixSort(vector< int > &SA ,vector< int > &RA ,int s ,int f ,int n){
    CountSort(SA ,RA ,s ,n); /// --- Sort By Second --- ///
    CountSort(SA ,RA ,f ,n); /// --- Sort By First  --- ///

    /// --- Sort The Pair ii(F ,S) --- ///
}

vector< int > ConstructSA(string &s ,int n){
    vector< int > tempRA(n ,0);
    vector< int > SA(n ,0) ,RA(n ,0);

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

    for(int k = 1 ; k < n && (RA[ SA[n - 1] ] != n - 1) ; k <<= 1 ){
        /// --- Sort pairs (RA[i] ,RA[i + k]) --- ///
        RadixSort(SA ,RA ,k ,0 ,n);

        /// --- Give New Ranks After Sorting --- ///
        int r = tempRA[ SA[0] ] = 0;
        for(int i = 1 ; i < n ; i++){
            bool flagF = (RA[ SA[i] ] == RA[ SA[i - 1] ]);
            bool flagS = (RA[ (SA[i] + k) >= n ? 0 : SA[i] + k ] ==
                          RA[ (SA[i - 1] + k) >= n ? 0 : SA[i - 1] + k ]);
            tempRA[ SA[i] ] = (flagF && flagS) ? r : ++r;
        }

        /// --- UPD Rank Array --- ///
        RA = tempRA;
    }

    return SA;
}

/// --- Find Str t in Str s --- ///
bool Search(vector< int > &Suff ,string &s ,int n ,string &t ,int m){
    bool Res = false;

    /// --- Binary Search The Suffixes --- ///
    int L = 0 ,R = n - 1;
    while( L <= R && !Res ){
        int Mid = (L + R) >> 1;

        string SubSuffString = SubStr(s ,Suff[Mid] ,m);

             if( SubSuffString < t ) L = Mid + 1;
        else if( SubSuffString > t ) R = Mid - 1;
        else Res = true;
    }

    return Res;
}

/// --- Count Occurs Of Str t in Str s --- ///
int CntOfOccInStr(vector< int > &Suff ,string &s ,int n ,string &t ,int m){

    /// --- Binary Search The Suffixes Get LowerBound --- ///
    int OccF;{
        int L = 0 ,R = n - 1;
        while( L <= R ){
            int Mid = (L + R) >> 1;

            string SubSuffString = SubStr(s ,Suff[Mid] ,m);

                 if( SubSuffString >= t ) R = Mid - 1;
            else if( SubSuffString <  t ) L = Mid + 1;
        }

        string  SubSuffString = SubStr(s ,Suff[L] ,m);
        OccF = (SubSuffString == t) ? L : -1;
    }

    /// --- Binary Search The Suffixes Get UpperBound --- ///
    int OccL;{
        int L = 0 ,R = n - 1;
        while( L <= R ){
            int Mid = (L + R) >> 1;

            string SubSuffString = SubStr(s ,Suff[Mid] ,m);

                 if( SubSuffString >  t ) R = Mid - 1;
            else if( SubSuffString <= t ) L = Mid + 1;
        }

        string  SubSuffString = SubStr(s ,Suff[R] ,m);
        OccL = (SubSuffString == t) ? R : -2;
    }

    int Cnt = OccL - OccF + 1;
    /// --- Ans = Idx OF UpperBound - Idx Of LowerBound + 1 --- ///
    return Cnt;
}

int main() {
    n = (int)(s = Read() + '$').size();

    vector< int > Suff = ConstructSA(s ,n);

    for(int i = 0 ; i < n ; i++ , puts("")){
        printf("%d %d " ,i ,Suff[i]);
        for(auto i : s.substr(Suff[i]))
            printf("%c" ,i);
    }
}