POJ.1509 Glass Beads

1.Problem
1509 -- Glass Beads (poj.org)

2.Idea
Suffix Array

3.Source Code

 const int MAXN = 20010;  
 int Rank[MAXN], tmp[MAXN];  
 int n, k;  
 int sa[MAXN];  
 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 string& s, int* sa) {  
      n = s.size();  
      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];  
      }  
 }  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S;  
           getInput(S);  
           createSA(S + S + (char)('z' + 1), sa);  
           int ans = -1;  
           for (int i = 0; i <= n; i++) {  
                if (sa[i] < S.length()) {  
                     ans = sa[i] + 1;  
                     break;  
                }  
           }  
           printf("%d\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }