notebook/code/SuffixArray.cpp

// Suffix array construction in O(L log^2 L) time.  Routine for
// computing the length of the longest common prefix of any two
// suffixes in O(log L) time.
// INPUT:   string s
// OUTPUT:  array suffix[] such that suffix[i] = index (from 0 to L-1)
//          of substring s[i...L-1] in the list of sorted suffixes.
//          That is, if we take the inverse of the permutation suffix[],
//          we get the actual suffix array.
struct SuffixArray {
  const int L;
  string s;
  VVI P;
  vector<pair<PII,int> > M;
  SuffixArray(const string &s) : L(s.length()), s(s), P(1, VI(L, 0)), M(L) {
    for(int i = 0; i < L; i++)
      P[0][i] = int(s[i]);
    for(int skip = 1, level = 1; skip < L; skip *= 2, level++) {
      P.push_back(VI(L, 0));
      for(int i = 0; i < L; i++)
        M[i] = make_pair(make_pair(P[level-1][i], i + skip < L ? P[level-1][i + skip] : -1000), i);
        sort(M.begin(), M.end());
        for(int i = 0; i < L; i++)
          P[level][M[i].second] = (i > 0 && M[i].first == M[i-1].first) ? P[level][M[i-1].second] : i;
    }
  }
  VI GetSuffixArray() { return P.back(); }
  // returns the length of the longest common prefix of s[i...L-1] and s[j...L-1]
  int LongestCommonPrefix(int i, int j) {
    int len = 0;
    if(i == j) return L - i;
    for(int k = P.size() - 1; k >= 0 && i < L && j < L; k--) {
      if (P[k][i] == P[k][j]) {
        i += 1 << k;
        j += 1 << k;
        len += 1 << k;
      }
    }
    return len;
  }
};
int test() {
  // bobocel is the 0'th suffix
  //  obocel is the 5'th suffix
  //   bocel is the 1'st suffix
  //    ocel is the 6'th suffix
  //     cel is the 2'nd suffix
  //      el is the 3'rd suffix
  //       l is the 4'th suffix
  SuffixArray suffix("bobocel");
  VI v = suffix.GetSuffixArray();
  // Expected output: 0 5 1 6 2 3 4
  //                  2
  for(int i = 0; i < v.size(); i++)
    cout << v[i] << " ";
  cout << endl;
  cout << suffix.LongestCommonPrefix(0, 2) << endl;
}