Skip to content

Instantly share code, notes, and snippets.

@soharu
Created August 27, 2013 11:58
Show Gist options
  • Save soharu/6352638 to your computer and use it in GitHub Desktop.
Save soharu/6352638 to your computer and use it in GitHub Desktop.
// 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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment