后缀数组，首先先将数组反转，从后往前做，此时的后缀就等于是原串的前缀，那么每添加一个前缀，增加了多少个不同的子串，其实就是在之前添加的前缀中，排名最靠近该前缀的两个串a和b，计算出他们与该前缀的lcp，然后不同的子串数就是当前添加的前缀长度len-max(lcpa,lcpb)了。具体实现维护排名可以用一个set维护，复杂度O(nlogn)。
代码
1 #include <cstdio> 2 #include <cstring> 3 #include<map> 4 #include<set> 5 using namespace std; 6 const int L = 110; 7 const int N = 1010; 8 9 const int MAXN = N*L; //数列的最大值和个数上界 10 11 struct SuffixArray{ 12 int wa[MAXN]; //用来进行基数排序或临时变量 13 int wb[MAXN]; //用来进行基数排序或临时变量 14 int wv[MAXN]; //用来进行基数排序或临时变量 15 int ws[MAXN]; //用来进行基数排序或临时变量 16 17 int sa[MAXN]; //sa[i]代表排名为i的后缀在原数列起始下标(数列的下标从0开始)，sa[0]肯定等于n，因为标兵为最小的。 18 int rank[MAXN]; //rank[i]代表suffix[i]的排名，rank[n]肯定等于0，理由同上。 19 int height[MAXN]; //height[i]代表排名为i - 1的后缀 和排名为i的后缀 的最长公共连续子序列 的长度。 20 int r[MAXN]; //r[]存放原数列下标从0到n，r[n]为a标兵，是r[]里面最小的. 21 int n; //数列的元素个数，不包括标兵 22 int m; //存放最大值，r[]数组的数都要小于m，用来进行基数排序 23 24 void input(int *val, int len, int Max){//Max要大于r[0..len - 1]，因为内部采用了基数排序 25 for (int i = 0;i < len;i++) 26 r[i] = val[i]; 27 r[len] = 0; //最小值，起标兵作用 28 n = len; 29 m = Max; 30 calSa(); 31 calHeight(); 32 } 33 34 int cmp(int *r, int a, int b, int l){ 35 return (r[a] == r[b] && r[a + l] == r[b + l]); 36 } 37 38 void calSa(){ //求sa数组 39 int i, j, p, *x = wa, *y = wb, *t; 40 for (i = 0;i < m;i++) ws[i] = 0; 41 for (i = 0;i < n + 1;i++) ws[x[i] = r[i]]++; 42 for (i = 1;i < m;i++) ws[i] += ws[i - 1]; 43 for (i = n;i >= 0;i--) sa[--ws[x[i]]] = i; 44 for (j = 1, p = 1;p < n + 1;j *= 2, m = p){ 45 for (p = 0, i = n - j + 1;i < n + 1;i++) y[p++] = i; 46 for (i = 0;i < n + 1;i++) if (sa[i] >= j) y[p++] = sa[i] - j; 47 for (i = 0;i < n + 1;i++) wv[i] = x[y[i]]; 48 for (i = 0;i < m;i++) ws[i] = 0; 49 for (i = 0;i < n + 1;i++) ws[wv[i]]++; 50 for (i = 1;i < m;i++) ws[i] += ws[i - 1]; 51 for (i = n;i >= 0;i--) sa[--ws[wv[i]]] = y[i]; 52 for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n + 1;i++) 53 x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; 54 } 55 } 56 57 void calHeight(){ //求rank和height数组 58 int i, j, k = 0; 59 for (i = 1;i <= n;i++) rank[sa[i]] = i; 60 for (i = 0;i < n;height[rank[i++]] = k) 61 for (k?k--:0, j = sa[rank[i]- 1];r[i + k] == r[j + k];k++); 62 } 63 //-求任意两后缀最长公共前缀问题，如果没用到可以去掉---------------------- 64 int Log[MAXN]; 65 int best[20][MAXN]; 66 void initRMQ() { //初始化RMQ 标准RMQ 预处理O(nlgn) 67 Log[0] = -1; 68 for(int i = 1;i <= MAXN;i++){ 69 Log[i]=(i & (i - 1))?Log[i - 1] : Log[i - 1] + 1 ; 70 } 71 for(int i = 1; i <= n ; i ++) best[0][i] = height[i]; 72 for(int i = 1; i <= Log[n] ; i ++) { 73 int limit = n - (1<<i) + 1; 74 for(int j = 1; j <= limit ; j ++) { 75 best[i][j] = (best[i-1][j] > best[i-1][j+(1<<i>>1)]) ? best[i-1][j+(1<<i>>1)] : best[i-1][j]; 76 } 77 } 78 } 79 int lcp(int a,int b) { //询问suffix[a]于suffix[b]的最长公共前缀(标准RMQ 询问O(1)) 使用这个函数之前要先后调用initRMQ()和input() 80 if(a > b){ 81 int t = a; 82 a = b; 83 b = t; 84 } 85 a ++; 86 int t = Log[b - a + 1]; 87 return (best[t][a] > best[t][b - (1<<t) + 1])? best[t][b - (1<<t) + 1] : best[t][a]; 88 } 89 }SA; 90 int n,i,a[MAXN],m,u,v,tot,len,t,tmp; 91 long long ans; 92 map<int,int> ma; 93 set<int> s; 94 set<int>::iterator it; 95 int main() 96 { 97 scanf("%d",&n); 98 for (i=0;i<n;i++) 99 { 100 scanf("%d",&a[i]); 101 if (ma[a[i]]==0) ma[a[i]]=++tot; 102 a[i]=ma[a[i]]; 103 } 104 for (i=0;i<n-1-i;i++) 105 { 106 t=a[i];a[i]=a[n-1-i];a[n-1-i]=t; 107 } 108 SA.input(a,n,tot+10); 109 SA.initRMQ(); 110 for (i=n-1;i>=0;i--) 111 { 112 len=n-i;tmp=0; 113 it=s.upper_bound(SA.rank[i]); 114 if (it!=s.end()) tmp=max(tmp,SA.lcp(*it,SA.rank[i])); 115 if (it!=s.begin()) tmp=max(tmp,SA.lcp(*(--it),SA.rank[i])); 116 s.insert(SA.rank[i]); 117 ans=ans+len-tmp; 118 printf("%lld ",ans); 119 } 120 121 }