1 #include <iostream> 2 #include <cstdlib> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 const int N = 100000 + 11; 8 int rank[N],wb[N],wv[N],wss[N],n; 9 int Sa[N],R[N]; 10 int f[N],height[N]; 11 12 13 14 15 bool cmp(int *r,int a,int b,int l) 16 { 17 return r[a] == r[b] && r[a+l] == r[b+l]; 18 } 19 20 void da(int *r,int *sa,int n,int m) 21 { 22 int i,j,p,*x = rank, *y = wb, *t; 23 for(i = 0; i < m; ++i) wss[i] = 0; 24 for(i = 0; i < n; ++i) ++wss[x[i]=r[i]]; 25 for(i = 1; i < m; ++i ) wss[i] += wss[i-1]; 26 for(i = n - 1; i >= 0; --i) sa[--wss[x[i]]] = i; 27 28 for(j = 1,p = 1; p < n; j *= 2, m = p) 29 { 30 for(p = 0,i = n - j; i < n; ++i) y[p++] = i; 31 for(i = 0; i < n; ++i)if(sa[i] >= j)y[p++] = sa[i] - j; 32 for(i = 0; i < n; ++i) wv[i] = x[y[i]]; 33 for(i = 0; i < m; ++i) wss[i] = 0; 34 for(i = 0; i < n; ++i) ++wss[wv[i]]; 35 for(i = 1; i < m; ++i) wss[i] += wss[i-1]; 36 for(i = n - 1; i >= 0; --i) sa[--wss[wv[i]]] = y[i]; 37 for(t = x, x = y, y = t,p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) 38 x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++; 39 40 } 41 42 } 43 44 void cal_height(int *r,int *sa,int n) 45 { 46 int i,j,k = 0; 47 for(i = 1; i <= n; ++i) f[sa[i]] = i; 48 for(i = 0; i < n; height[f[i++]] = k) 49 for(k?k--:0,j = sa[f[i]-1] ;r[i+k] == r[j+k]; ++k); 50 51 } 52 53 char ss[N]; 54 int main() 55 { 56 scanf("%s",ss); 57 int l = strlen(ss); 58 for(int i = 0; i < l; ++i) R[i] = ss[i]; R[l] = 0; 59 da(R,Sa,l + 1,128); 60 cal_height(R,Sa,l); 61 62 return 0; 63 }