fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Uzumaki Naruto :)
  5.  
  6. #define DB(a) cerr << __LINE__ << ": " << #a << " = " << (a) << endl
  7. #define dbg(A,sz) for(int i = 0; i < sz; ++i) cerr << A[i] << " "; cerr << "\n"
  8. #define CLR(A,sz) for(int i = 0; i < sz; ++i) A[i] = 0;
  9. #define pause() cin.get();cin.get();
  10. typedef long long LL;
  11. typedef pair<int,int> PII;
  12. typedef vector<int> VI;
  13.  
  14. const int MM = 1123;
  15. const int NN = 112345;
  16.  
  17. int od[20][NN],t[NN][2];
  18. int A[NN],B[NN],C[NN],D[NN];
  19.  
  20. int st[MM],ed[MM],Map[NN];
  21. int nxt[NN],prev[NN];
  22. int Mstp,Mcnt,N,sz;
  23. string inp[MM],fin;
  24.  
  25. void Build(){
  26.     CLR(A,300);
  27.     for(int i = 0; i < sz; ++i) A[(int)fin[i]] = 1;
  28.     for(int i = 1; i < 300; ++i) A[i] += A[i-1];
  29.     for(int i = 0; i < sz; ++i)
  30.         od[0][i] = A[(int)fin[i]];
  31.  
  32.     CLR(A,300);
  33.     int stp = 1, cnt = 1,k;
  34.     for(; cnt < sz; cnt <<= 1, ++stp){
  35.         CLR(A,sz+10);
  36.         CLR(B,sz+10);
  37.  
  38.         for(int i = 0; i < sz; ++i)
  39.             ++A[t[i][0] = od[stp-1][i]], ++B[t[i][1] = ((i+cnt < sz) ? od[stp-1][i+cnt] : 0)];
  40.         for(int i = 1; i <= sz; ++i)
  41.             A[i] += A[i-1], B[i] += B[i-1];
  42.         for(int i = sz-1; i >= 0; --i)
  43.             C[--B[t[i][1]]] = i;
  44.         for(int i = sz-1; i >= 0; --i)
  45.             k = C[i], D[--A[t[k][0]]] = k;
  46.  
  47.         k = od[stp][D[0]] = 1;
  48.         for(int i = 1; i < sz; ++i){
  49.             int id1 = D[i], id2 = D[i-1];
  50.             od[stp][id1] = (k += (t[id1][1] != t[id2][1] or t[id1][0] != t[id2][0]));
  51.         }
  52.     }
  53.     Mcnt = cnt, Mstp = stp-1;
  54. }
  55.  
  56. int LCP(int x,int y){
  57.     if (x == -1 or y == -1) return 0;
  58.     int res = 0, stp = Mstp , cnt = Mcnt;
  59.     for(; stp >= 0; --stp, cnt >>= 1)
  60.         if (x+cnt <= sz and y+cnt <= sz and od[stp][x] == od[stp][y])
  61.             res += cnt, x += cnt, y += cnt;
  62.     return res;
  63. }
  64.  
  65. void solve(){
  66.     cin >> N;
  67.     fin = ""; sz = 0;
  68.  
  69.     for(int i = 0; i < N; ++i) {
  70.         cin >> inp[i];
  71.         st[i] = sz, ed[i] = sz+(int)inp[i].size()-1;
  72.         for(int j = 0; j < (int)inp[i].size(); ++j)
  73.             Map[sz++] = i, fin.push_back(inp[i][j]);
  74.     }
  75.  
  76.     assert(sz < NN);
  77.     Build();
  78.     int i = 0, j = 0;
  79.     while(i < sz){
  80.         while(j < sz and Map[D[j]] == Map[D[i]]) ++j;
  81.         int ans = (j < sz ? D[j] : -1);
  82.         while(i < j) nxt[D[i++]] = ans;
  83.     }
  84.  
  85.     i = j = sz-1;
  86.     while(i >= 0){
  87.         while(j >= 0 and Map[D[j]] == Map[D[i]]) --j;
  88.         int ans = (j >= 0 ? D[j] : -1);
  89.         while(i > j) prev[D[i--]] = ans;
  90.     }
  91.  
  92.     for(int i = 0; i < N; ++i){
  93.         int ans = INT_MAX,id,res;
  94.         for(int j = st[i]; j <= ed[i]; ++j){
  95.             int p1 = LCP(j,nxt[j]), p2 = LCP(j,prev[j]);
  96.             res = max(p1,p2);
  97.             if (res >= ed[i]-j+1) continue;
  98.             if (res < ans) ans = res, id = j;
  99.         }
  100.         assert(ans != INT_MAX);
  101.         for(int j = 0; j <= ans; ++j) cout << fin[id+j];
  102.         cout << "\n";
  103.     }
  104. }
  105.  
  106. int main()
  107. {
  108. 	ios_base::sync_with_stdio(0);
  109. 	cin.tie(NULL);
  110. 	solve();
  111. 	return 0;
  112. }
  113.  
Success #stdin #stdout 0s 15608KB
comments (?)
stdin
copy 
3
abcm
acm
bcd
stdout
copy 
ab
ac
d
https://ideone.com/8veKxE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!