Suffix Array Construction

Question

I'm trying to implement a suffix array for use in programming competitions. I'm using the CodeForces example and trying to "make it my own" so I can make sure I understand it and feel better about using it.

Here's what I have so far:

struct SuffixArray {
    vector<int> sa, pos, tmp;
    int n, gap;

    SuffixArray(string s) {
        n = s.length();
        sa = pos = tmp = vector<int>(n);
        for (int i=0; i<n; i++) sa[i] = i, pos[i] = s[i], tmp[i] = 0;
        for (gap = 1;; gap *= 2) {
            quickSort(sa, n, 0, n - 1);
            for (int i=0; i<n-1; i++) tmp[i+1] = tmp[i] + sufCmp(sa[i], sa[i+1]);
            for (int i=0; i<n; i++) pos[sa[i]] = tmp[i];
            if (tmp[n-1] == n - 1) break;
        }
    }

    bool sufCmp(int i, int j) {
        if (pos[i] != pos[j]) return pos[i] < pos[j];
        i += gap;
        j += gap;
        return (i < n && j < n) ? pos[i] < pos[j] : i > j;
    }

    int partition(vector<int> &arr, int lo, int hi) {
        int p = arr[hi];
        int pi = lo;
        for (int i=lo; i<hi; i++) {
            if (sufCmp(arr[i], p)) {
                swap(arr[i], arr[pi]);
                pi++;
            }
        }
        swap(arr[hi], arr[pi]);
        return pi;
    }

    void quickSort(vector<int> &arr, int sz, int lo, int hi) {
        if (lo < hi) {
            int p = partition(arr, lo, hi);
            quickSort(arr, sz, lo, p-1);
            quickSort(arr, sz, p+1, hi);
        }
    }
};

This works, but it is hopelessly slower than the original. On this problem from SPOJ, it scores in the range expected by a naive solution which is \$O(n^2 \log n)\$.

My question is, why? My guess is it either has to do with the way I am storing and accessing data (wrapping everything in a struct, using vectors instead of pre-allocated arrays), or it could be an issue with my quickSort implementation (since the suffix array will already be 'mostly' sorted on all but the first iteration, using the last element as pivot could be bad), but I don't understand enough about what's going on under the hood to be sure.

I tested the pivot theory by using the middle element instead of the last element as the pivot for the quicksort... still way too slow.

Answer 1

vector<int> 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 & s to avoid unnecessary copying of the string.

for (int i=0; i<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<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?