#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


struct suffix
{
    int index;
    int rank[2];
};

bool operator<(const struct suffix& a, const struct suffix& b)
{
    if (a.rank[0] == b.rank[0])
    {
        if (a.rank[1] < b.rank[1])
            return true;
        else
            return false;
    }
    else if (a.rank[0] < b.rank[0])
        return true;
    else
        return false;

}

int getMax(suffix arr[], int n)
{

    suffix mx = arr[0];
    for (int i = 1; i < n; ++i)
        if (mx < arr[i])
            mx = arr[i];

    int max_val = (mx.rank[0] < mx.rank[1]) ? mx.rank[1] : mx.rank[0];

    return max_val+1;
}

bool operator == (const struct suffix& a, const struct suffix& b)
{
    return (a.rank[0] == b.rank[0] && a.rank[1] == b.rank[1]);
}

void radix_sort(suffix A[], int n)
{

    suffix B[n];
    int max_val = getMax(A, n);
    int C[max_val];


    int d, tmp, count;


    for (int i = 1; i > -1; --i)
    {
        cout << "i= " << i << endl;
        for (int j = 0; j < max_val; ++j)
        {
            C[j] = 0;
        }

       cout << "000" << endl;
        for (int j = 0; j < n; ++j)
        {
            d = A[j].rank[i];

            C[d]++;
            cout << "d , C[d] = " << d << " " << C[d] << endl;

        }
        cout << "C1" << endl;
        for (int k=0 ; k < max_val; ++k)
        {
            cout << C[k] << " ";
        }
        cout << endl;

        count = 0;
        for (int j = 0; j < max_val; ++j)
        {
            tmp = C[j];
            C[j] = count;
            count += tmp;
        }

        cout << "C2" << endl;
        for (int k=0 ; k < max_val; ++k)
        {
            cout << C[k] << " ";
        }
        cout << endl;

        cout <<"asbs"<<endl;
        for (int j = 0; j < n; ++j)
        {
            d = A[j].rank[i];
            if (d != -1)
            {
                cout << "d , C[d] = " << d << " " << C[d] << endl;
                B[C[d]] = A[j];
                C[d]++;
            }
        }

        cout << "B" << endl;
        for (int k=0 ; k < n-1; ++k)
        {
            //cout << " k= " << k << endl;
            cout << B[k].rank[0] << " " << B[k].rank[1] << endl;
        }

        for (int j = 0; j < n; ++j)
        {
            A[j] = B[j];
        }

        cout << "==========" << endl;
    }

}


int* get_suff_array(char* str, int n)
{
    suffix suffixes[n];

    for (int i = 0; i < n; ++i)
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = str[i] - 'a';

        if (i + 1 < n)
            suffixes[i].rank[1] = str[i + 1] - 'a';
        else
            suffixes[i].rank[1] = -1;
    }

    radix_sort(suffixes, n);

    int pos_to_suff_idx[n];

    for (int k = 4; k < 2 * n; k = k * 2)
    {
        int rank = 0;
        int prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        pos_to_suff_idx[suffixes[0].index] = 0;

        for (int i = 1; i < n; ++i)
        {
            // if suffixes[i-1] == suffixes[i] or suffixes[i].rank[0] == suffixes[i - 1].rank[0]
            if (suffixes[i].rank[0] == prev_rank && suffixes[i].rank[1] == suffixes[i - 1].rank[1])
            {
                // prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            }
            else
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            pos_to_suff_idx[suffixes[i].index] = i;
        }

        for (int next_idx, suff_idx, i = 0; i < n; ++i)
        {
            next_idx = suffixes[i].index + k / 2;
            if (next_idx < n)
            {
                suff_idx = pos_to_suff_idx[next_idx];
                suffixes[i].rank[1] = suffixes[suff_idx].rank[0];
            }
            else
            {
                suffixes[i].rank[1] = -1;
            }
        }

        radix_sort(suffixes, n);
    }

    int *suff_array = new int[n];
    for (int i = 0; i < n; ++i)
        suff_array[i] = suffixes[i].index;

    return suff_array;
}

void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    char txt[] = "banana";
    int n = strlen(txt);
    int* suffixArr = get_suff_array(txt, n);
    cout << "Following is suffix array for " << txt << endl;
    printArr(suffixArr, n);
    return 0;
}