URAL 1517 Freedom of Choice

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define pii pair<int,int>
15 #define INF 0x3f3f3f3f
16 using namespace std;
17 const int maxn = 200020;
18 int rk[maxn],wb[maxn],wv[maxn],wd[maxn],lcp[maxn];
19 bool cmp(int *r,int i,int j,int k){
20     return r[i] == r[j] && r[i+k] == r[j+k];
21 }
22 void da(int *r,int *sa,int n,int m){
23     int i,k,p,*x = rk,*y = wb;
24     for(i = 0; i < m; ++i) wd[i] = 0;
25     for(i = 0; i < n; ++i) wd[x[i] = r[i]]++;
26     for(i = 1; i < m; ++i) wd[i] += wd[i-1];
27     for(i = n-1; i >= 0; --i) sa[--wd[x[i]]] = i;
28 
29     for(p = k = 1; p < n; k <<= 1, m = p){
30         for(p = 0,i = n-k; i < n; ++i) y[p++] = i;
31         for(i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;
32         for(i = 0; i < n; ++i) wv[i] = x[y[i]];
33         for(i = 0; i < m; ++i) wd[i] = 0;
34         for(i = 0; i < n; ++i) wd[wv[i]]++;
35         for(i = 1; i < m; ++i) wd[i] += wd[i-1];
36         for(i = n-1; i >= 0; --i) sa[--wd[wv[i]]] = y[i];
37 
38         swap(x,y);
39         x[sa[0]] = 0;
40         for(p = i = 1; i < n; ++i)
41             x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
42     }
43 }
44 void calcp(int *r,int *sa,int n){
45     for(int i = 1; i <= n; ++i) rk[sa[i]] = i;
46     int h = 0;
47     for(int i = 0; i < n; ++i){
48         if(h > 0) h--;
49         for(int j = sa[rk[i]-1]; j+h < n && i+h < n; ++h)
50             if(r[i+h] != r[j+h]) break;
51         lcp[rk[i]-1] = h;
52     }
53 }
54 char sc[maxn],sb[maxn];
55 int sa[maxn],r[maxn];
56 int main() {
57     int len;
58     while(~scanf("%d",&len)){
59         scanf("%s",sc);
60         scanf("%s",sb);
61         sc[len] = ‘\0‘;
62         strcpy(sc+len+1,sb);
63         for(int i = 0; i < (len<<1|1); ++i)
64              r[i] = sc[i];
65         r[len<<1|1] = 0;
66         da(r,sa,(len<<1)+2,128);
67         calcp(r,sa,len<<1|1);
68         int ans = 0,index = 0;
69         for(int i = 1; i < (len<<1|1); ++i){
70             if(sa[i] < len != sa[i+1] < len){
71                 if(lcp[i] > ans){
72                     ans = lcp[i];
73                     index = sa[i];
74                 }
75             }
76         }
77         for(int i = 0; i < ans; ++i)
78             putchar(sc[index+i]);
79         putchar(‘\n‘);
80     }
81     return 0;
82 }