notebook/code/SuffixArray.cpp

// Routine for computing the length of the longest common prefix of any two
// suffixes
const int maxn = 1000;
struct SuffixArray {
	char s[maxn];      //original string, the last character must be 0 and there is no 0 before.
	int sa[maxn];     //sa[i] = the index of the i-th smallest suffix.
	int rrank[maxn];   //rank[i] = rank of the suffix of index i. rank[0] must be n-1.
	int height[maxn]; // height[i] = The length of the longest common prefix of sa[i-1] and sa[i]
	int t[maxn], t2[maxn], c[maxn]; // aux
	int n; // the number of character.
	void clear() {
    n = 0;
    memset(sa, 0, sizeof(sa));
    memset(t, 0 , sizeof(t));
    memset(t2, 0 , sizeof(t2));
	}
	// m = max(char) + 1;
	//Build the suffix array of string s, every character should be between 0 and m-1.
	// initialiser s and n before calling this function.
	void build_sa(int m) {
    int i, *x = t, *y = t2;
    for(i = 0; i < m; i++) c[i] = 0;
    for(i = 0; i < n; i++) c[x[i] = s[i]]++;
    for(i = 1; i < m; i++) c[i] += c[i-1];
    for(i = n-1; i >= 0; i--) sa[--c[x[i]]] = i;
    for(int k = 1; k <= n; k <<= 1) {
      int p = 0;
      for(i = n-k; i < n; i++) y[p++] = i;
      for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k;
      for(i = 0; i < m; i++) c[i] = 0;
      for(i = 0; i < n; i++) c[x[y[i]]]++;
      for(i = 0; i < m; i++) c[i] += c[i-1];
      for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
      swap(x, y);
      p = 1; x[sa[0]] = 0;
      for(i = 1; i < n; i++)
      x[sa[i]] = y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k] ? p-1 : p++;
      if(p >= n) break;
      m = p;
    }
	}
	void build_height() {
		int i, k = 0;
  	for(i = 0; i < n; i++) rrank[sa[i]] = i;
  	for(i = 0; i < n; i++) {
      if(k) k--;
      int j = sa[rrank[i]-1];
      while(s[i+k] == s[j+k]) k++;
      height[rrank[i]] = k;
  	}
	}
	//The LCP of any two suffx = RMQ(height[i+1],...,height[j])
};
void test() {
 	SuffixArray SA;
	strcpy(SA.s, "1122330");
	SA.clear();
	SA.n = strlen(SA.s);
	SA.build_sa(100);
	SA.build_height();
	for (int i = 0; i < SA.n; i++)
		cout << i << " " << SA.s[i] << " " << SA.sa[i] << " " << SA.rrank[i] << endl;
}