UOzqpm - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll mx=200001;
ll sa[mx],lcp[mx],pos[mx],tmp[mx];
string a;
ll d=1,n;
bool cmp(ll x,ll y){
    if(pos[x]!=pos[y]) return pos[x]<pos[y];
    x+=d;y+=d;
    return x<n&&y<n?pos[x]<pos[y]:x>y;
}
void findSA(){
    for(ll i=0;i<n;++i){
        sa[i]=i;
        pos[i]=a[i];
    }
    for(d=1;;d<<=1){
    	sort(sa,sa+n,cmp);
        tmp[0]=0;
        for(ll i=1;i<n;++i) tmp[i]=tmp[i-1]+cmp(sa[i-1],sa[i]);
        for(ll i=0;i<n;++i) pos[sa[i]]=tmp[i];

        for(int i =0;i<n;++i){
        	cout<<tmp[i]<<" "<<a.substr(sa[i])<<endl;
        }
        cout<<a<<endl;
        for(int i =0;i<n;++i) cout<<pos[i];cout<<endl;
        for(int i =0;i<n;++i) cout<<sa[i];cout<<endl;
        if(/*tmp[n-1]==n-1 ||*/ d>=n) break;
    }
}
int main() {
	a = "BANANANA";
	n = a.size();
	cout<<a<<endl;
	findSA();
	// your code goes here
	return 0;
}