学习了后缀数组，顺便把DC3算法也看了一下，传说中可以O(n)复杂度求出文本串的height，先比较一下倍增算法和DC3算法好辣。
DC3 倍增法
时间复杂度 O(n)(但是常数很大) O(nlogn)(常数较小)
空间复杂度 O(n) O(n)
编程复杂度 较高 较低
由于在时间复杂度上DC3的常数比较大，再加上编程复杂度比较高，所以在解决问题的时候并不是最优选择。但是学到了后缀数组还是补充一下的好点。
DC3算法的实现：
1：先把文本串的后缀串分成两部分，第一部分是后缀串i mod 3 == 0, 第二部分是i mod 3 != 0，然后先用基数排序对第二部分后缀串排序(按照前三个字符进行排序)。
1 int *san = sa+n, *rn = r+n, ta=0, tb=(n+1)/3, tbc=0, i, j, p; 2 //ta i mod 3==0的个数，tb i mod 3==1的个数， tbc imod3!=0的个数 3 for (i=0; i<n; i++) 4 if (i % 3) 5 x[tbc ++] = i; 6 7 r[n] = r[n+1] = 0;//在文本串后面添加两个0，便于处理 8 Sort (r+2, x, y, tbc, m); 9 Sort (r+1, y, x, tbc, m); 10 Sort (r, x, y, tbc, m);
然后把suffix[1]与suffix[2]数组连起来，每三个相邻的字符看做一个数，变成这个样子：
操作代码如下：
1 rn[F(y[0])] = 0; 2 for (i=1, p=1; i<tbc; i++) 3 rn[F(y[i])] = c0(r, y[i-1], y[i])?p-1:p++; 4 //#define F(x) x/3+(x%3==1?0:tb) 5 //F(x) 求原字符串suffix(i)在新串中的位置
如果p>=tbc的话，也就是说只排列前三个字符就可以区分出第二部分后缀串的顺序了，否则就要进行递归继续对第二部分的串进行排序。
1 if (p < tbc) 2 DC3 (rn, san, tbc, p); 3 else 4 for (i=0; i<tbc; i++) 5 san[rn[i]] = i;
2：对第一部分后缀来说：
suffix[3*i] = r[3*i] + suffix[3*i+1];
suffix[3*j] = r[3*j] + suffix[3*j+1]; 我们已知i mod 3 == 1 的所有suffix[i]的顺序了，可以利用基数排序很快的求出第一部分后缀的顺序。
1 for (i=0; i<tbc; i++) 2 if (san[i] < tb) 3 y[ta++] = san[i]*3; 4 if (n%3 == 1) 5 //对于n%3==1时，不存在suffix[n-1] == r[n] + suffix[n]; 6 y[ta++] = n - 1; 7 Sort (r, y, x, ta, m);//对mod3==0的后缀串排序
3：第一部分后缀数组和第二部分后缀数组都排好序以后，可以对两部分后缀数组进行一次简单的归并排序，然后sa数组就完美呈现了。
1 //#define G(x) x>=tb?(x-tb)*3+2:x*3+1 2 //新文本串中suffix(i)在原文本串中的位置 3 for (i=0; i<tbc; i++) 4 c[y[i] = G(san[i])] = i; 5 for (i=0, j=0, p=0; i<ta&&j<tbc; p++) 6 sa[p] = c12 (y[j]%3, r, y[j], x[i])?y[j++]:x[i++]; 7 for (; j<tbc; j++) 8 sa[p++] = y[j]; 9 for (; i<ta; i++) 10 sa[p++] = x[i];
c12就是比较第一部分与第二部分串的大小：
suffix [3*i] = r[3*i] + suffix[3*i+1];
suffix [3*j+1] = r[3*j+1] + suffix[3*j+2]; 已知suffix[3*i+1]与suffix[3*i+2]所对应的大小关系，可以比较r[3*i]与r[3*j+1]的大小得出最终结果。
suffix [3*i] = r[3*i] + suffix[3*i+1];
suffix [3*j+2] = r[3*j+2] + suffix[3*(j+1)]; 这个我们可以先比较 r[3*i] 与 r[3*j+2] 的大小，然后再比较 suffix[3*i+1] 与 suffix[3*(j+1)] ，这样就把问题转化为了第一种情况咯。
1 bool c12 (int k, int *r, int a, int b) 2 {//return 真 suffix[b]大，return false suffix[a]大 3 if (k == 1) 4 return r[a]<r[b] || (r[a]==r[b]&&c[a+1]<c[b+1]); 5 return r[a]<r[b] || (r[a]==r[b]&&c12(1, r, a+1, b+1)); 6 }
对于和后缀数组相关的这两个算法，其实并没有什么难点。难理解的点就在于基数排序对数组的使用，手动模拟几遍就OK辣！
最后再附上一个完整的DC3代码
1 #define F(x) x/3+(x%3==1?0:tb) 2 #define G(x) x>=tb?(x-tb)*3+2:x*3+1 3 4 const int maxn = 110; 5 int c[maxn*3], x[maxn*3], y[maxn*3]; 6 int sa[maxn*3], rank[maxn*3]; 7 8 bool c0 (int *r, int a, int b) 9 { 10 return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2]; 11 } 12 13 bool c12 (int k, int *r, int a, int b) 14 { 15 //return 真 suffix[b]大，return false suffix[a]大 16 if (k == 1) 17 return r[a]<r[b] || (r[a]==r[b]&&c[a+1]<c[b+1]); 18 return r[a]<r[b] || (r[a]==r[b]&&c12(1, r, a+1, b+1)); 19 } 20 21 void Sort (int *r, int *a, int *b, int n, int m) 22 { 23 for (int i=0; i<m; i++) c[i] = 0; 24 for (int i=0; i<n; i++) c[r[a[i]]] ++; 25 for (int i=1; i<m; i++) c[i] += c[i-1]; 26 for (int i=n-1; i>=0; i--) 27 b[--c[r[a[i]]]] = a[i]; 28 } 29 30 void DC3 (int *r, int *sa, int n, int m) 31 { 32 int *san = sa+n, *rn = r+n, ta=0, tb=(n+1)/3, tbc=0, i, j, p; 33 for (i=0; i<n; i++) if (i % 3) x[tbc ++] = i; 34 35 r[n] = r[n+1] = 0; 36 Sort (r+2, x, y, tbc, m); 37 Sort (r+1, y, x, tbc, m); 38 Sort (r, x, y, tbc, m); 39 40 rn[F(y[0])] = 0; 41 for (i=1, p=1; i<tbc; i++) 42 rn[F(y[i])] = c0(r, y[i-1], y[i])?p-1:p++; 43 //rn[i] 起始位置为i的排名 44 45 if (p < tbc) 46 DC3 (rn, san, tbc, p); 47 else 48 for (i=0; i<tbc; i++) 49 san[rn[i]] = i; 50 51 for (i=0; i<tbc; i++) 52 if (san[i] < tb) 53 y[ta++] = san[i]*3; 54 55 if (n%3 == 1) 56 y[ta++] = n - 1; 57 58 Sort (r, y, x, ta, m);//对mod3==0的后缀串排序 59 for (i=0; i<tbc; i++) 60 c[y[i] = G(san[i])] = i; 61 62 for (i=0, j=0, p=0; i<ta&&j<tbc; p++) 63 sa[p] = c12 (y[j]%3, r, y[j], x[i])?y[j++]:x[i++]; 64 for (; j<tbc; j++) 65 sa[p++] = y[j]; 66 for (; i<ta; i++) 67 sa[p++] = x[i]; 68 69 return; 70 }