Suffix Array Construction
vector&lt;int&gt; sa, pos, tmp;
int n, gap;



Surely you could come up with better variable names than these? Also, tmp and sa are only used inside the constructor, so they should be local variables, not struct members.


SuffixArray(string s)



This should be const string &amp; s to avoid unnecessary copying of the string.


for (int i=0; i&lt;n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = 0;



The comma operator has a few legitimate uses, but this is not one of them. Coding it this way will lead to problems if you need to modify the loop body at all. The right way to do this is to make a multi-statement loop the usual way: curly braces surrounding multiple lines with one statement on each line.

 for (int i=0; i&lt;n; i++)
 {
   sa[i] = i;
   pos[i] = s[i];
   tmp[i] = 0;
 }



     for (gap = 1;; gap *= 2) {



Why do you have a for loop with an empty termination condition?