Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int p1 = 1e9 + 7, p2 = 1e9 + 9;
- long long bin_pow(int a, int n, int m)
- {
- if(n == 0)
- return 1;
- if(n == 1)
- return a;
- long long t = bin_pow(a, n / 2, m);
- return (((t * t) % m) * (n % 2 ? a : 1)) % m;
- }
- int main()
- {
- // Ускорение ввода
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- // Ввод/вывод из файла
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- // Ввод
- int n;
- cin >> n;
- int prev, cur;
- cin >> prev;
- long long hash_a[n];
- hash_a[0] = 0;
- for(int i = 1; i < n; i++)
- {
- cin >> cur;
- hash_a[i] = (hash_a[i - 1] + ((cur - prev + 1) * bin_pow(p1, i, p2)) % p2) % p2;
- prev = cur;
- }
- int m;
- cin >> m;
- cin >> prev;
- long long hash_b = 0;
- for(int i = 1; i < m; i++)
- {
- cin >> cur;
- hash_b = (hash_b + ((cur - prev + 1) * bin_pow(p1, i, p2)) % p2) % p2;
- prev = cur;
- }
- m--, n--;
- for(int i = m; i <= n; i++)
- {
- if((hash_a[i] - hash_a[i - m] + p2) % p2 == hash_b)
- {
- cout << i - m + 1;
- exit(0);
- }
- hash_b = (hash_b * p1) % p2;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement