推荐博客：
所谓的后缀数组，就是将字符串的 n 个后缀全部取出来，采用字典序的排序方式，将排序好的后缀开头位置顺次放进数组中。
在后缀数组中，有几个关键的变量
1 . SA 数组，若 sa[ i ] = j ,所表示的含义是排名为 i 的后缀起始下标是 j ，
2 . rank数组，若rank[ i ] = j,所表示的含义是以 i 为开头的后缀的排名是 j，
3 . height数组，所表示的suffix(sa[i])和suffix(sa[i-1])的最长公共前缀，即排名相邻的两个后缀的最长公共前缀
4 .h数组， 所表示的含义是 h[i] = height[rank[i]]，即 suffix(i)和在有序数列中排在它前一名后缀的最长公共前缀。
suffix(j) 和 suffix(k)的最长公共前缀为 min(height[rank[j]+1], height[rank[j]+2], … height[rank[k]])
接下来就是构造后缀数组，有两种方法，一种是倍增的算法（n*logn）
const int maxn = 2e4+5;/*-待排序数组长度为 n，放在 0~n-1,在最后加一个'$',让其比所有的字符串中的字符都小，这样既可以满足字典序的要求，也不越界*build_sa( ,n+1, );//注意是n+1;*getheight(,n);*例如：*n = 8;*num[] = { 1, 1, 2, 1, 1, 1, 1, 2, $ };注意num最后一位为0，其他大于0*rank[] = { 4, 6, 8, 1, 2, 3, 5, 7, 0 };rank[0~n-1]为有效值，rank[n]必定为0无效值*sa[] = { 8, 3, 4, 5, 0, 6, 1, 7, 2 };sa[1~n]为有效值，sa[0]必定为n是无效值*height[]= { 0, 0, 3, 2, 3, 1, 2, 0, 1 };height[2~n]为有效值*/int n; int a[maxn], s[maxn];int sa[maxn], rank[maxn], height[maxn];int t1[maxn], t2[maxn], c[maxn];bool cmp(int *r, int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; // !!!}void build_sa(int n, int m){ //m代表估计数字，是ASCll的最大值 int *x = t1, *y = t2; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) c[x[i]=s[i]]++; for(int i = 1; i < m; i++) c[i] += c[i-1]; for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; for(int j = 1; j <= n; j <<= 1){ // !!! int p = 0; for(int i = n-j; i < n; i++) y[p++] = i; for(int i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i]-j; for(int i = 0; i < m; i++) c[i] = 0; for(int i = 0; i < n; i++) c[x[y[i]]]++; for(int i = 1; i < m; i++) c[i] += c[i-1]; for(int i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; // !!! for(int i = 1; i < n; i++) x[sa[i]] = cmp(y, sa[i-1], sa[i], j)?p-1:p++; if (p >= n) break; m = p; // 下次基数排序的最大值 !!! }}void getheight(){ int k = 0; for(int i = 0; i <= n; i++) rank[sa[i]] = i; for(int i = 0; i < n; i++){ if (k) k--; int j = sa[rank[i]-1]; while(s[i+k] == s[j+k]) k++; height[rank[i]] = k; }}