Advertisement
ivnikkk

Untitled

Dec 26th, 2022
1,141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define int long long
  6. const int mod = 1e9 + 9;
  7. const int b1 = 16063807ll, b2 = 964027ll, mod1 = 1e9 + 7, mod2 = 998244353;
  8. struct Hash {
  9.     vector<pair<int, int>> h, p;
  10.     Hash(int n, vector<int>& a) {
  11.         h.resize(n + 1), p.resize(n + 1);
  12.         h[0] = {0, 0};
  13.         p[0] = {1, 1};
  14.         for (int i = 0; i < n; i++) {
  15.             h[i + 1].first = (h[i].first * b1 + a[i]) % mod1;
  16.             h[i + 1].second = (h[i].second * b2 + a[i]) % mod2;
  17.             p[i + 1].first = (p[i].first * b1) % mod1;
  18.             p[i + 1].second = (p[i].second * b2) % mod2;
  19.         }
  20.     }
  21.     pair<int, int> get_hash(int l, int r) {
  22.         int left = (h[r + 1].first - (h[l].first * p[r - l + 1].first) % mod1 + mod1) % mod1;
  23.         int right = (h[r + 1].second - (h[l].second * p[r - l + 1].second) % mod2 + mod2) % mod2;
  24.         return {left, right};
  25.     }
  26. };
  27. signed main() {
  28. #ifdef _DEBUG
  29.     freopen("input.txt", "r", stdin);
  30.     freopen("output.txt", "w", stdout);
  31. #endif
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(nullptr);
  34.     int n, m; cin >> n >> m;
  35.     vector<int> a(n), b(m);
  36.     for (int i = 0; i < n; i++) {
  37.         cin >> a[i];
  38.     }
  39.     for (int i = 0; i < m; i++) {
  40.         cin >> b[i];
  41.     }
  42.     Hash a_bck(n, a), b_bck(m, b);
  43.     reverse(all(a)); reverse(all(b));
  44.     Hash a_fr(n, a), b_fr(m, b);
  45.     auto hash_pair = [&](pair<int, int>& x) {
  46.         return (x.first + (x.second * b1) % mod) % mod;
  47.     };
  48.     int ans = 1;
  49.     for (int _ = 0; _ < 2; _++) {
  50.         auto ok = [&](int tm) {
  51.             unordered_set<int> st;
  52.             for (int i = tm; i + tm - 1 + _ < n; i++) {
  53.                 pair<int, int> left = a_bck.get_hash(i - tm, i - 1);
  54.                 pair<int, int> right = a_fr.get_hash(n - 1 - (i + _ + tm - 1), n - 1 - (i + _));
  55.                 swap(left, right);
  56.                 left.first = (left.first - right.first + mod1) % mod1;
  57.                 left.second = (left.second - right.second + mod2) % mod2;
  58.                 st.insert(hash_pair(left));
  59.             }
  60.             for (int i = tm; i + tm - 1 + _ < m; i++) {
  61.                 pair<int, int> left = b_bck.get_hash(i - tm, i - 1);
  62.                 pair<int, int> right = b_fr.get_hash(m - 1 - (i + _ + tm - 1), m - 1 - (i + _));
  63.                 left.first = (left.first - right.first + mod1) % mod1;
  64.                 left.second = (left.second - right.second + mod2) % mod2;
  65.                 if (st.count(hash_pair(left))) {
  66.                     return true;
  67.                 }
  68.             }
  69.             return false;
  70.         };
  71.         int l = 0, r = n / 2 + 10;
  72.         while (r - l > 1) {
  73.             int tm = (r + l) / 2;
  74.             if (ok(tm)) {
  75.                 l = tm;
  76.             }
  77.             else {
  78.                 r = tm;
  79.             }
  80.         }
  81.         ans = max(ans, l * 2 + _);
  82.     }
  83.     cout << ans;
  84. }
  85.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement