Suffix array

#include<bits/stdc++.h>
using namespace std;
int const maxn=1e5+10;
string s;
int n,sa[maxn],isa[maxn],lcp[maxn];
int sas[maxn],is[maxn],pos[maxn];
void gen_Sa()
{
    for(int i=0;i<n;++i)
        sa[i]=i;
    sort(sa,sa+n,[&](int o1,int o2){return s[o1]<s[o2];});
    /*for(int i=0;i<n;++i)
        cout<<sa[i]<<' ';
    cout<<endl;*/
    for(int i=1;i<n;++i)
        isa[sa[i]]=(s[sa[i]]!=s[sa[i-1]])?i:isa[sa[i-1]];
    /*for(int i=0;i<n;++i)
        cout<<isa[sa[i]]<<' ';
    cout<<endl;*/
    for(int len=1;len<n;len*=2)
    {
        for(int i=0;i<n;++i)
        {
            sas[i]=sa[i];
            pos[i]=i;
            is[i]=isa[i];
        }
        for(int w,i=0;i<n;++i)
        {
            w=(sas[i]-len<0)?sas[i]-len+n:sas[i]-len;
            sa[pos[is[w]]++]=w;
        }
        for(int i=1;i<n;++i)
            isa[sa[i]]=(is[sa[i-1]]==is[sa[i]]&&is[(sa[i-1]+len)%n]==is[(sa[i]+len)%n])?isa[sa[i-1]]:i;
    }
}
void genLCP()
{
    int k=0;
    for(int j,i=0;i<n-1;++i)
    {
        j=sa[isa[i]-1];
        cout<<j<<' '<<sa[isa[i]-1]<<endl;
        while(j+k<n&&i+k<n&&s[i+k]==s[j+k])++k;
        lcp[isa[i]-1]=k;
        if(k)--k;
    }
}
int main()
{
    cin>>s;
    s+='$';
    n=s.size();
    gen_Sa();
    for(int i=0;i<n;++i)
        cout<<sa[i]<<' '<<isa[sa[i]]<<endl;
    cout<<endl;
    cout<<endl;
    genLCP();
    for(int i=0;i<n;++i)
        cout<<lcp[i]<<' ';
    cout<<endl;
return 0;
}
/*
banana

$
a 1
ana 3
anana 0
banana 0
na 2
nana 0


abaaba

$
a 1
aaba 1
aba 3
abaaba 0
ba 2
baaba 0
*/