POJ.3581 Sequence

1.Problem
http://poj.org/problem?id=3581

2.Idea
Suffix Array

3.Source

 const int MAXN = 20010;  
 namespace SA {  
      int rank[2 * MAXN], tmp[2 * MAXN];  
      int n, k;  
      bool compare_sa(int i, int j) {  
           if (rank[i] != rank[j]) return rank[i] < rank[j];  
           int ri = (i + k <= n) ? rank[i + k] : -1;  
           int rj = (j + k <= n) ? rank[j + k] : -1;  
           return ri < rj;  
      }  
      void createSA(const int* s, int N, int* sa) {  
           n = N;  
           for (int i = 0; i <= n; i++) {  
                sa[i] = i;  
                rank[i] = i < n ? s[i] : -1;  
           }  
           for (k = 1; k <= n; k *= 2) {  
                sort(sa, sa + n + 1, compare_sa);  
                tmp[sa[0]] = 0;  
                for (int i = 1; i <= n; i++) {  
                     tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);  
                }  
                for (int i = 0; i <= n; i++) rank[i] = tmp[i];  
           }  
      }  
 }  
 int N, A[MAXN], rev[2 * MAXN], sa[2 * MAXN];  
 void solve()  
 {  
      cin >> N;  
      for (int i = 0; i < N; i++) scanf("%d", A + i);  
      reverse_copy(A, A + N, rev);  
      SA::createSA(rev, N, sa);  
      int p1, p2;  
      for (int i = 0; i <= N; i++) {  
           p1 = N - sa[i];  
           if (p1 > 0 && N - p1 >= 2) break;  
      }  
      int m = N - p1;  
      reverse_copy(A + p1, A + N, rev);  
      reverse_copy(A + p1, A + N, rev + m);  
      SA::createSA(rev, 2 * m, sa);  
      for (int i = 0; i <= 2 * m; i++) {  
           p2 = m - sa[i];  
           if (p2 > 0 && m - p2 >= 1) break;  
      }  
      for (int i = p1 - 1; i >= 0; i--) printf("%d\n", A[i]);  
      for (int i = p1 + p2 - 1; i >= p1; i--) printf("%d\n", A[i]);  
      for (int i = N - 1; i >= p1 + p2; i--) printf("%d\n", A[i]);  
 }  
 int main() {  
      //ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }