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