Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define int long long
- const int mod = 1e9 + 9;
- const int b1 = 16063807ll, b2 = 964027ll, mod1 = 1e9 + 7, mod2 = 998244353;
- struct Hash {
- vector<pair<int, int>> h, p;
- Hash(int n, vector<int>& a) {
- h.resize(n + 1), p.resize(n + 1);
- h[0] = {0, 0};
- p[0] = {1, 1};
- for (int i = 0; i < n; i++) {
- h[i + 1].first = (h[i].first * b1 + a[i]) % mod1;
- h[i + 1].second = (h[i].second * b2 + a[i]) % mod2;
- p[i + 1].first = (p[i].first * b1) % mod1;
- p[i + 1].second = (p[i].second * b2) % mod2;
- }
- }
- pair<int, int> get_hash(int l, int r) {
- int left = (h[r + 1].first - (h[l].first * p[r - l + 1].first) % mod1 + mod1) % mod1;
- int right = (h[r + 1].second - (h[l].second * p[r - l + 1].second) % mod2 + mod2) % mod2;
- return {left, right};
- }
- };
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m; cin >> n >> m;
- vector<int> a(n), b(m);
- for (int i = 0; i < n; i++) {
- cin >> a[i];
- }
- for (int i = 0; i < m; i++) {
- cin >> b[i];
- }
- Hash a_bck(n, a), b_bck(m, b);
- reverse(all(a)); reverse(all(b));
- Hash a_fr(n, a), b_fr(m, b);
- auto hash_pair = [&](pair<int, int>& x) {
- return (x.first + (x.second * b1) % mod) % mod;
- };
- int ans = 1;
- for (int _ = 0; _ < 2; _++) {
- auto ok = [&](int tm) {
- unordered_set<int> st;
- for (int i = tm; i + tm - 1 + _ < n; i++) {
- pair<int, int> left = a_bck.get_hash(i - tm, i - 1);
- pair<int, int> right = a_fr.get_hash(n - 1 - (i + _ + tm - 1), n - 1 - (i + _));
- swap(left, right);
- left.first = (left.first - right.first + mod1) % mod1;
- left.second = (left.second - right.second + mod2) % mod2;
- st.insert(hash_pair(left));
- }
- for (int i = tm; i + tm - 1 + _ < m; i++) {
- pair<int, int> left = b_bck.get_hash(i - tm, i - 1);
- pair<int, int> right = b_fr.get_hash(m - 1 - (i + _ + tm - 1), m - 1 - (i + _));
- left.first = (left.first - right.first + mod1) % mod1;
- left.second = (left.second - right.second + mod2) % mod2;
- if (st.count(hash_pair(left))) {
- return true;
- }
- }
- return false;
- };
- int l = 0, r = n / 2 + 10;
- while (r - l > 1) {
- int tm = (r + l) / 2;
- if (ok(tm)) {
- l = tm;
- }
- else {
- r = tm;
- }
- }
- ans = max(ans, l * 2 + _);
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement