Advertisement
GerONSo

Untitled

Feb 15th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.09 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.  
  57. int prefix_function (string s) {
  58. int n = (int) s.length();
  59. vector<int> pi (n);
  60. for (int i=1; i<n; ++i) {
  61. int j = pi[i-1];
  62. while (j > 0 && s[i] != s[j])
  63. j = pi[j-1];
  64. if (s[i] == s[j]) ++j;
  65. pi[i] = j;
  66. }
  67. return pi.back();
  68. }
  69.  
  70. void dfs(int u) {
  71. used[u] = 1;
  72. for(auto v : g[u]) {
  73. if(!used[v.x]) {
  74. dfs(v.x);
  75. }
  76. if(used[v.x] != 1) {
  77. if(dp[u] < dp[v.x] + v.y) {
  78. dp[u] = dp[v.x] + v.y;
  79. par[u] = v.x;
  80. }
  81. }
  82. }
  83. used[u] = 2;
  84. }
  85.  
  86. signed main() {
  87. seriy();
  88. int n;
  89. cin >> n;
  90. vector<string> s(n);
  91. int sum = 0;
  92. string ans = "";
  93. for(int i = 0; i < n; i++) {
  94. cin >> s[i];
  95. ans += s[i];
  96. sum += s[i].size();
  97. }
  98. g.resize(n);
  99. for(int i = 0; i < n; i++) {
  100. for(int j = 0; j < n; j++) {
  101. if(i == j) continue;
  102. string k = s[i] + '#' + s[j];
  103. int pi = prefix_function(k);
  104. g[j].push_back({i, pi});
  105. string res = "";
  106. for(auto p : s[j]) {
  107. res += p;
  108. }
  109.  
  110. k = s[j] + '#' + s[i];
  111. pi = prefix_function(k);
  112. g[i].push_back({j, pi});
  113. }
  114. }
  115. int mx = 0;
  116.  
  117. for(int i = 0; i < n; i++) {
  118. dp.resize(n, 0);
  119. used.resize(n, 0);
  120. par.resize(n, -1);
  121. dfs(i);
  122. if(mx < dp[i]) {
  123. mx = dp[i];
  124. int cur = i;
  125. string kek = "";
  126. cerr << i << " ";
  127. for(auto i : par) {
  128. cerr << i << " ";
  129. }
  130. cerr << '\n';
  131. // while(cur != -1) {
  132. // kek += s[cur];
  133. // cur = par[cur];
  134. // }
  135. // ans = kek;
  136. }
  137. }
  138. cout << ans;
  139. return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement