Advertisement
Guest User

Untitled

a guest
Oct 14th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. int const maxn = 4e6 + 7;
  6. long long const mod = 1000000007;
  7. map<char, int> suff[maxn];
  8. int link[maxn], len[maxn], k, from[maxn];
  9. int sz = 2, last = 1;
  10. string word;
  11. char a[200007];
  12.  
  13. bitset<10> cnt[maxn];
  14.  
  15. char sym[maxn];
  16.  
  17.  
  18. bool used[maxn];
  19.  
  20. void input() {
  21. cin >> k;
  22. }
  23.  
  24.  
  25. inline void extend(char c) {
  26. int curr = sz++;
  27. sym[curr] = c;
  28. from[curr] = last;
  29. len[curr] = len[last] + 1;
  30. int p;
  31. for (p = last; p != 0 && !suff[p][c]; p = link[p]) {
  32. suff[p][c] = curr;
  33. }
  34. if (p == 0) {
  35. link[curr] = 1;
  36. } else {
  37. int q = suff[p][c];
  38. if (len[p] + 1 == len[q]) {
  39. link[curr] = q;
  40. } else {
  41. int clone = sz++;
  42. from[clone] = p;
  43. sym[clone] = sym[q];
  44. len[clone] = len[p] + 1;
  45. link[clone] = link[q];
  46. suff[clone] = suff[q];
  47. for (; p != 0 && suff[p][c] == q; p = link[p]) {
  48. suff[p][c] = clone;
  49. }
  50. link[q] = link[curr] = clone;
  51. }
  52. }
  53. last = curr;
  54. }
  55.  
  56. void deep_dfs(int v) {
  57. if ((int) sym[v] < 97) {
  58. cnt[v][(int) sym[v] - 60] = true;
  59. return;
  60. }
  61. used[v] = true;
  62. for (auto it:suff[v]) {
  63. if (!used[it.second]) {
  64. deep_dfs(it.second);
  65. }
  66. cnt[v] |= cnt[it.second];
  67. }
  68. }
  69.  
  70.  
  71. void solve() {
  72. sym[1] = 'a';
  73. for (int i = 0; i < k; i++) {
  74. cin >> word;
  75. for (size_t j = 0; j < word.length(); j++) {
  76. extend(word[j]);
  77. }
  78. extend((char) (60 + i));
  79. }
  80. fill(used, used + maxn, false);
  81. deep_dfs(1);
  82. int ans = 0, ind = 1;
  83. for (int i = 2; i < sz; i++) {
  84. if (cnt[i].count() == k) {
  85. if (len[i] > ans) {
  86. ans = len[i];
  87. ind = i;
  88. }
  89. }
  90. }
  91. int pos = 0;
  92. for (; ind != 1; ind = from[ind]) {
  93. a[pos] = sym[ind];
  94. pos++;
  95. }
  96. for (int i = pos - 1; i >= 0; i--) {
  97. cout << a[i];
  98. }
  99.  
  100. }
  101.  
  102. int32_t main() {
  103. IOS
  104. input();
  105. solve();
  106. return 0;
  107.  
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement