Skip to content

Instantly share code, notes, and snippets.

@chadbrewbaker
Created July 10, 2011 14:20
Show Gist options
  • Save chadbrewbaker/1074578 to your computer and use it in GitHub Desktop.
Save chadbrewbaker/1074578 to your computer and use it in GitHub Desktop.
Simple STL suffix array example v2
//Simple STL suffix array example
/*
crb002$ ./a.out
inv suffix array: 7 6 0 4 1 5 3 2
suffix array: 2 4 7 6 3 5 1 0
source: 0 0 1 1 0 1 0 0
The sort took 29 comparison operations.
*/
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int myints[] = {0,0,1,1,0,1,0,0};
int lu[] = {0,1,2,3,4,5,6,7};
int MY_STRING_LENGTH = 8;
int COMPARES = 0;
bool suffCompare(int a,int b) {
int max = a;
if(a==b)
return 0;
if(a<b)
max = b;
while (max < MY_STRING_LENGTH) {
COMPARES++;
if( myints[lu[a]] != myints[lu[b]])
return myints[lu[a]] < myints[lu[b]];
a++;
b++;
max++;
}
if(a==MY_STRING_LENGTH); //if one is the end of string
return 1;
if(b==MY_STRING_LENGTH);
return 0;
}
int main () {
vector<int> myvector (lu, lu+8);
vector<int> sourcevector(myints, myints+8);
vector<int>::iterator it;
int sa[8];
sort (myvector.begin(), myvector.end(), suffCompare);
cout << "inv suffix array:";
int i=0;
for (it=myvector.begin(); it!=myvector.end(); ++it){
cout << " " << *it;
sa[*it]=i;
i++;
}
cout << endl;
cout << " suffix array:";
i=0;
for (it=myvector.begin(); it!=myvector.end(); ++it){
cout << " " << sa[i];
i++;
}
cout << endl;
cout << " source:";
for (it=sourcevector.begin(); it!=sourcevector.end(); ++it)
cout << " " << *it;
cout << endl;
cout << "The sort took " << COMPARES << " comparison operations." << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment