SuffixArray

#include <cstdio>
#include <cstring>

#define MAX 100010

char str[MAX];
int n, suffixArray[MAX];

void countingSort(int *ranking, int k)
{
    int maxi=n>300?n:300, freq[maxi],temp[MAX];

    memset(freq,0,sizeof freq);

    for(int i=0;i<n;i++)
    {
        if(i+k<n) freq[ranking[i+k]]++;
        else freq[0]++;
    }

    for(int i=0,sum=0,t;i<maxi;i++) t=freq[i], freq[i]=sum, sum+=t;

    for(int i=0;i<n;i++)
    {
        int x=suffixArray[i]+k;
        
        if(x<n) temp[freq[ranking[x]]]=suffixArray[i], freq[ranking[x]]++;
        else temp[freq[0]]=suffixArray[i], freq[0]++;
    }

    for(int i=0;i<n;i++) suffixArray[i]=temp[i];
}

void process()
{
    int r, temp[MAX], ranking[MAX];

    for(int i=0;i<n;i++) ranking[i]=str[i], suffixArray[i]=i;
    
    for(int k=1;k<n;k<<=1)
    {
        countingSort(ranking,k);
        countingSort(ranking,0);

        temp[suffixArray[0]]=r=0;

        for(int i=1;i<n;i++)
        {
            if(ranking[suffixArray[i]]==ranking[suffixArray[i-1]] && ranking[suffixArray[i]+k]==ranking[suffixArray[i-1]+k])
                temp[suffixArray[i]]=r;
            else
                temp[suffixArray[i]]=++r;
        }

        for(int i=0;i<n;i++) ranking[i]=temp[i];

        if(ranking[suffixArray[n-1]]==n-1) break;
    }
}

int main()
{
    strcpy(str,"ABACBDBCDBAABCDEAB$");
    n=strlen(str);
    process();
    for(int i=0;i<n;i++) printf("%2d\t%s\n", suffixArray[i], str+suffixArray[i]);
}