Advertisement
Guest User

Untitled

a guest
Feb 24th, 2017
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:16777216")
  3.  
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <string>
  9. #include <unordered_map>
  10. #include <queue>
  11.  
  12. using namespace std;
  13.  
  14. const int p = 239, m = 1e9 + 7;
  15. vector < int > pw, hs;
  16.  
  17. struct st
  18. {
  19.     int len, d, cn;
  20.     int hs;
  21.     st() {}
  22.     st(int len, int d, int hs, int cn) : len(len), d(d), hs(hs), cn(cn) {}
  23. };
  24.  
  25. st up(st a, int l, int nw) {
  26.     if (a.d > 0) {
  27.         if (l == a.d) {
  28.             return st(a.len + a.d, 0, 0ll, a.cn + 1);
  29.         }
  30.         if (l < a.d) {
  31.             return st(a.len + l, a.d - l, a.hs - nw * pw[a.d - l], a.cn + 1);
  32.         }
  33.         if (l > a.d) {
  34.             return st(a.len + a.d, a.d - l, nw - a.hs * pw[l - a.d], a.cn + 1);
  35.         }
  36.     }
  37.     else {
  38.         a.d = -a.d;
  39.         auto ans = up(a, l, nw);
  40.         ans.d = -ans.d;
  41.         return ans;
  42.     }
  43. }
  44.  
  45. unordered_map < int, vector < pair < int, int > > > q;
  46. unordered_map < int, pair < st, int > > pr;
  47. unordered_map < int, bool > us;
  48. vector < vector < int > > hsh;
  49. st ans(-1, 0, 0ll, 0);
  50.  
  51. int hh(st a) {
  52.     return a.hs * p * p + a.len * p + a.d;
  53. }
  54.  
  55. bool bfs(st cur) {
  56.     queue < st > w;
  57.     w.push(cur);
  58.     us[hh(cur)] = 1;
  59.     while (!w.empty()) {
  60.         auto now = w.front();
  61.         w.pop();
  62.         int h = hh(now);
  63.         if (now.len > 20000)
  64.             continue;
  65.         if (!now.d && now.len && now.cn > 2) {
  66.             ans = now;
  67.             return 1;
  68.         }
  69.         for (auto i : q[now.hs]) {
  70.             auto nx = up(now, i.second, hs[i.first]);
  71.             int n = hh(nx);
  72.             if (!us[n]) {
  73.                 pr[n] = { now, i.first };
  74.                 w.push(nx);
  75.                 us[n] = 1;
  76.             }
  77.         }
  78.     }
  79.     return 0;
  80. }
  81.  
  82. int main() {
  83.     iostream::sync_with_stdio(0);
  84.     int n;
  85.     cin >> n;
  86.     pw.resize(101, 1);
  87.     for (int i = 1; i < 101; i++)
  88.         pw[i] = pw[i - 1] * p;
  89.     hs.resize(n);
  90.     vector < string > a(n);
  91.     hsh.resize(n);
  92.     for (int i = 0; i < n; i++) {
  93.         cin >> a[i];
  94.         hsh[i].resize(a[i].length() + 1, 0);
  95.         for (int j = 1; j <= a[i].length(); j++)
  96.             hsh[i][j] = hsh[i][j - 1] * p + a[i][j - 1];
  97.         hs[i] = hsh[i][a[i].length()];
  98.     }
  99.     for (int i = 0; i < n; i++) {
  100.         for (int j = 0; j < n; j++) {
  101.             if (i == j)
  102.                 continue;
  103.             for (int len = 1; len <= a[i].length(); len++) {
  104.                 int now = min(len, (int)a[j].length());
  105.                 int h = hsh[i][a[i].length()] - hsh[i][a[i].length() - len] * pw[len];
  106.                 int h1 = hsh[i][a[i].length() - (len - now)] - hsh[i][a[i].length() - len] * pw[now];
  107.                 int h2 = hsh[j][now];
  108.                 if (h1 == h2) {
  109.                     q[h].push_back({ j, a[j].length() });
  110.                 }
  111.             }
  112.         }
  113.     }
  114.     for (int i = 0; i < n; i++) {
  115.         int h = hh(st(0, a[i].length(), hsh[i][a[i].length()], 1));
  116.         pr[h] = { st(0, 0, 0, 0), i };
  117.         if (bfs(st(0, a[i].length(), hsh[i][a[i].length()], 1)))
  118.             break;
  119.     }
  120.     if (ans.len == -1) {
  121.         cout << "NO\n";
  122.         return 0;
  123.     }
  124.     cout << "YES\n";
  125.     st start = st(0, 0, 0, 0);
  126.     vector < string > ans1, ans2;
  127.     while ((start.d != ans.d) || (start.len != ans.len) || (start.hs != ans.hs) || (start.cn != ans.cn)) {
  128.         int h = hh(ans);
  129.         auto p = pr[h].first;
  130.         if (ans.d > p.d) {
  131.             ans1.push_back(a[pr[h].second]);
  132.         }
  133.         else {
  134.             ans2.push_back(a[pr[h].second]);
  135.         }
  136.         ans = pr[h].first;
  137.     }
  138.     reverse(ans1.begin(), ans1.end());
  139.     for (string s : ans1)
  140.         cout << s;
  141.     return 0;
  142. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement