Advertisement
GerONSo

Untitled

Feb 17th, 2020
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.25 KB | None | 0 0
  1. /*
  2.  
  3. ∧_∧
  4. ( ・ω・。)つ━☆・*。
  5. ⊂  ノ    ・゜
  6. しーJ   Accepted
  7.  
  8. */
  9.  
  10.  
  11.  
  12. // #pragma GCC optimize("O3")
  13. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  14.  
  15. #include <bits/stdc++.h>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. #define ll long long
  20. #define all(x) begin(x), end(x)
  21. #define x first
  22. #define y second
  23. #define int long long
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef long double ld;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(14);
  39. #ifdef _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 2e5 + 10;
  46. const int MAXM = 600;
  47. const int INF = 1e18 + 7;
  48. const int BASE = 47;
  49. const int MOD = 998244353;
  50. const int MAXLOG = 61;
  51. const ld EPS = 1e-8;
  52.  
  53. vector<vector<pair<int, int>>> g;
  54. vector<int> dp, used, par;
  55. map<pair<int, int>, string> mp;
  56. vector<string> s;
  57. string ans;
  58. int n;
  59.  
  60. int prefix_function (string s) {
  61. int n = (int) s.length();
  62. vector<int> pi (n);
  63. for (int i=1; i<n; ++i) {
  64. int j = pi[i-1];
  65. while (j > 0 && s[i] != s[j])
  66. j = pi[j-1];
  67. if (s[i] == s[j]) ++j;
  68. pi[i] = j;
  69. }
  70. return pi.back();
  71. }
  72.  
  73. void dfs(int u, string cur, int dep) {
  74. used[u] = 1;
  75. for(auto v : g[u]) {
  76. if(!used[v.x]) {
  77. string nw = cur + s[v.x].substr(v.y, s[v.x].size() - v.y);
  78. dfs(v.x, nw, dep + 1);
  79. }
  80. }
  81. if(dep == n - 1) {
  82. // cerr << cur << '\n';
  83. if(ans.size() > cur.size()) {
  84. ans = cur;
  85. }
  86. }
  87. }
  88.  
  89. void add(string &s, string &t) {
  90. string k = t + '#' + s;
  91. int pi = prefix_function(k);
  92. s += t.substr(pi, t.size() - pi);
  93. }
  94.  
  95. signed main() {
  96. seriy();
  97.  
  98. cin >> n;
  99. s.resize(n);
  100. int sum = 0;
  101. for(int i = 0; i < n; i++) {
  102. cin >> s[i];
  103. ans += s[i];
  104. sum += s[i].size();
  105. }
  106. mt19937 rr(time(0));
  107. g.resize(n);
  108. for(int i = 0; i < n; i++) {
  109. for(int j = 0; j < n; j++) {
  110. if(i == j) continue;
  111. // string k = s[i] + '#' + s[j];
  112. // int pi = prefix_function(k);
  113. // g[j].push_back({i, pi});
  114. // string res = "";
  115. // for(auto p : s[j]) {
  116. // res += p;
  117. // }
  118.  
  119. string k = s[j] + '#' + s[i];
  120. int pi = prefix_function(k);
  121. g[i].push_back({j, pi});
  122. }
  123. sort(all(g[i]), [&](pair<int, int> a, pair<int, int> b) {
  124. return a.y > b.y;
  125. });
  126. }
  127. int mx = 0;
  128. used.resize(n, 0);
  129. for(int i = 0; i < n; i++) {
  130.  
  131. string res = "";
  132. fill(all(used), 0);
  133. for(int j = 0; j < 2; j++) {
  134. add(res, s[j]);
  135. used[j] = 1;
  136. }
  137.  
  138. dfs(i, res, 1);
  139. // cerr << ans << '\n';
  140. }
  141. cout << ans;
  142. return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement