suffix_array.cpp

// Suffix Array from JMBook
// 
//

#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>

using namespace std;

struct Comparator {
    const vector<int> &group;
    int t;
    Comparator(const vector<int> &group, int t): group(group), t(t) {}
    bool operator() (int a, int b)
    {
        if (group[a] != group[b])
            return group[a] < group[b];
        return group[a + t] < group[b + t];
    }
};

void print_step(int t, const vector<int> & group, const vector<int> &perm)
{
    printf("t = %d\n", t);
    printf("group:\n");
    for (size_t i = 0; i < group.size(); ++i)
        printf("group[%ld] = %d\n", i, group[i]);
    printf("perm :\n");
    for (size_t i = 0; i < perm.size(); ++i)
        printf(" perm[%ld] = %d\n", i, perm[i]);
    scanf("%*c");
}

vector<int> get_suffix_array(const string &str)
{
    int n = str.size();
    vector<int> group(n + 1);
    for (int i = 0; i < n; ++i)
        group[i] = str[i];
    group[n] = -1;

    vector<int> perm(n);
    for (int i = 0; i < n; ++i)
        perm[i] = i;

    //print_step(0, group, perm);
    int t = 1;
    while (t < n)
    {
        Comparator comp(group, t);
        sort(perm.begin(), perm.end(), comp);
        //print_step(t, group, perm);
        t *= 2;

        if (t >= n)
            break;

        vector<int> newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[perm[0]] = 0;
        for (int i = 1; i < n; ++i)
        {
            if (comp(perm[i - 1], perm[i]))
                newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
            else
                newGroup[perm[i]] = newGroup[perm[i - 1]];
        }
        group = newGroup;
    }
    return perm;
}

int main()
{
    string str("banana");
    vector<int> suffix_array = get_suffix_array(str);
    for (size_t i = 0; i < suffix_array.size(); ++i)
        printf("%lu = %d\n", i, suffix_array[i]);
    return 0;
}