titovtima

Untitled

Oct 21st, 2020
1,105
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <cmath>
  6. #include <map>
  7. #include <queue>
  8. #include <list>
  9. #include <set>
  10.  
  11. //freopen(".in", "r", stdin);
  12. //freopen(".out", "w", stdout);
  13.  
  14. using namespace std;
  15. using ld = long double;
  16. using ll = long long;
  17. using ull = unsigned long long;
  18. using pii = pair<int,int>;
  19.  
  20. int main() {
  21.     ios::sync_with_stdio(0);
  22.     cin.tie(0);
  23.     cout.tie(0);
  24.  
  25.     int n;
  26.     cin >> n;
  27.  
  28.     string s1, s2;
  29.     cin >> s1 >> s2;
  30.  
  31.     char sep1 = (char) ('A' - 1);
  32.     char sep2 = (char) ('A' - 2);
  33. //    char sep = (char)('A'-1);
  34.  
  35. //    vector<string> v1;
  36. //    v1.push_back(s1 + sep);
  37. //
  38. //    while (v1[v1.size()][n] != sep)
  39. //        v1.push_back(v1[v1.size()-1].substr(1) + v1[v1.size()-1][0]);
  40. //
  41. //    vector<string> v2;
  42. //    v2.push_back(s2 + sep);
  43. //
  44. //    while (v2[v2.size()][n] != sep)
  45. //        v2.push_back(v2[v2.size()-1].substr(1) + v2[v2.size()-1][0]);
  46. //
  47. //    sort(v1.begin(), v1.begin());
  48. //    sort(v2.begin(), v2.begin());
  49.  
  50.     string s = s1 + sep1 + s2 + sep2;
  51.  
  52. //    vector<string> v(1, s);
  53. //    for (int i = 0; i < 2 * n + 1; i++)
  54. //        v.push_back(v[i].substr(1) + v[i][0]);
  55. //
  56. //    sort(v.begin(), v.end());
  57.  
  58.     string reals;
  59.  
  60.     vector<int> recode('Z'+2);
  61.     vector<int> count('Z'+2);
  62.     for (int i = 0; i < s.size(); i++)
  63.         count[s[i]]++;
  64.  
  65.     int numb = 0;
  66.     for (char i = 'A' - 2; i <= 'Z'; i++) {
  67.         if (count[i] > 0) {
  68.             recode[i] = numb;
  69.             numb++;
  70.         }
  71.     }
  72.  
  73. //        for (int i = 0; i < s.size(); i++)
  74. //            reals += s[i];
  75.     reals = s;
  76.  
  77. //        cout << s << "\n" << reals << "\n";
  78.  
  79.     for (int i = 0; i < s.size(); i++)
  80.         s[i] = recode[s[i]];
  81.  
  82.  
  83.     vector<int> p(s.size());
  84.  
  85.     vector<int> c(s.size());
  86.     vector<int> cnt(s.size());
  87.  
  88. //    vector<pair<char,int>> st(s.size());
  89. //    for (int i = 0; i < s.size(); i++)
  90. //        st[i] = {s[i], i};
  91. //    sort(st.begin(), st.end());
  92. //
  93. //    for (int i = 0; i < s.size(); i++)
  94. //        p[i] = st[i].second;
  95.  
  96.     for (int i = 0; i < s.size(); i++)
  97.         cnt[s[i]]++;
  98.     for (char i = 1; i < s.size(); i++)
  99.         cnt[i] += cnt[i - 1];
  100.     for (int i = s.size() - 1; i >= 0; i--) {
  101.         cnt[s[i]]--;
  102.         p[cnt[s[i]]] = i;
  103.         c[i] = s[i];
  104.     }
  105.  
  106.     for (int len = 1; len < s.size(); len *= 2) {
  107.         vector<int> q(s.size());
  108.         vector<int> cNew(s.size());
  109.         for (int i = 0; i < s.size(); i++)
  110.             q[i] = (p[i] - len + s.size()) % s.size();
  111.         cnt = vector<int>(s.size());
  112.         for (int i = 0; i < s.size(); i++)
  113.             cnt[c[i]]++;
  114.         for (int i = 1; i < s.size(); i++)
  115.             cnt[i] += cnt[i - 1];
  116.         for (int i = s.size() - 1; i >= 0; i--) {
  117.             cnt[c[q[i]]]--;
  118.             p[cnt[c[q[i]]]] = q[i];
  119.         }
  120.         cNew[p[0]] = 0;
  121.         for (int i = 1; i < s.size(); i++) {
  122.             int a = p[i];
  123.             int b = p[i - 1];
  124.             cNew[p[i]] = cNew[p[i - 1]];
  125.             if (c[a] != c[b] || c[(a + len) % s.size()] != c[(b + len) % s.size()])
  126.                 cNew[p[i]]++;
  127.         }
  128.         for (int i = 0; i < s.size(); i++)
  129.             c[i] = cNew[i];
  130.     }
  131.  
  132.  
  133.     vector<bool> pos(s.size());
  134.     for (int i = 0; i < s.size(); i++)
  135.         pos[i] = p[i] <= s1.size();
  136.  
  137. //    vector<int> p(v.size());
  138. //    vector<bool> pos(v.size());
  139. //    for (int i = 0; i < v.size(); i++) {
  140. //        pos[i] = v[i].find(sep2) < v[i].find(sep1);
  141. //        p[i] = v.size() - v[i].find(sep2) - 1;
  142. //    }
  143.  
  144.     vector<int> lcp(s.size());
  145.  
  146.  
  147.     vector<int> inv(s.size());
  148.     for (int i = 0; i < s.size(); i++)
  149.         inv[p[i]] = i;
  150.  
  151.     int k = 0;
  152.     for (int i = 0; i < s.size(); i++) {
  153.         if (inv[i] == s.size() - 1) {
  154.             lcp[inv[i]] = 0;
  155.             k = 0;
  156.             continue;
  157.         }
  158.         int j = p[inv[i] + 1];
  159.         while (max(i + k, j + k) < s.size() && s[i + k] == s[j + k])
  160.             k++;
  161.         lcp[inv[i]] = k;
  162.         k = max(0, k - 1);
  163.     }
  164.  
  165.  
  166.     string ans;
  167.     for (int i = 0; i < s.size() - 1; i++) {
  168.         if ((pos[i] != pos[i + 1]) && lcp[i] > ans.size()) {
  169. //            ans = v[i].substr(0, lcp[i]);
  170.             ans = reals.substr(p[i], lcp[i]);
  171.         }
  172.     }
  173.  
  174. //    for (int i = 0; i < v.size(); i++)
  175. //        cout << v[i] << " " << lcp[i] << "\n";
  176.  
  177. //    for (int i = 0; i < s.size(); i++)
  178. //        cout << p[i] << " " << lcp[i] << " " << reals.substr(p[i]) << " " << pos[i] << "\n";
  179.  
  180.     cout << ans << "\n";
  181.  
  182.     return 0;
  183. }
  184.  
  185. /*
  186. 3
  187. ABA
  188. BAA
  189.  
  190. 4
  191. ABBA
  192. BAAA
  193.  
  194.  */
RAW Paste Data