POJ.2217 Secretary

1.Problem
2217 -- Secretary (poj.org)

2.Idea
Suffix Array
Longest Common Prefix Array

3. Source Code

 const int MAXN = 20010;  
 namespace SA {  
      int rank[MAXN], tmp[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 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];  
           }  
      }  
      namespace LCP {  
           int rank[MAXN];  
           void createLCP(const string& s, const int* sa, int* lcp) {  
                int n = s.size();  
                for (int i = 0; i <= n; i++) rank[sa[i]] = i;  
                int h = 0;  
                lcp[0] = 0;  
                for (int i = 0; i < n; i++) {  
                     int j = sa[rank[i] - 1];  
                     h = max(0, h - 1);  
                     for (; j + h < n && i + h < n; h++) {  
                          if (s[j + h] != s[i + h]) break;  
                     }  
                     lcp[rank[i] - 1] = h;  
                }  
           }  
      } // namespace LCP  
 } // namespace SA  
 char str[MAXN];  
 void getInput(string& s) {  
      fgets(str, MAXN, stdin);  
      strtok(str, "\n\0");  
      s = str;  
 }  
 int sa[MAXN], lcp[MAXN];  
 void solve()  
 {  
      int t;  
      scanf("%d\n", &t);  
      while (t--) {  
           string S, T;  
           getInput(S); getInput(T);  
           int n = S.size(), m = T.size();  
           S += '\n';  
           S += T;  
           SA::createSA(S, sa);  
           SA::LCP::createLCP(S, sa, lcp);  
           int nm = S.size(), ans = 0;  
           for (int i = 0; i < nm; i++) {  
                if (sa[i] < n && sa[i + 1] < n) continue;  
                if (sa[i] > n && sa[i + 1] > n) continue;  
                ans = max(ans, lcp[i]);  
           }  
           printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);  
      }  
 }  
 int main() {  
      ios_base::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(13);  
      solve();  
      return 0;  
 }