Created
July 10, 2011 14:20
-
-
Save chadbrewbaker/1074578 to your computer and use it in GitHub Desktop.
Simple STL suffix array example v2
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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