Advertisement
Guest User

D(hash)

a guest
Jan 19th, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int p1 = 1e9 + 7, p2 = 1e9 + 9;
  6.  
  7. long long bin_pow(int a, int n, int m)
  8. {
  9.     if(n == 0)
  10.         return 1;
  11.     if(n == 1)
  12.         return a;
  13.  
  14.     long long t = bin_pow(a, n / 2, m);
  15.     return (((t * t) % m) * (n % 2 ? a : 1)) % m;
  16. }
  17.  
  18. int main()
  19. {
  20.     // Ускорение ввода
  21.     ios_base::sync_with_stdio(0);
  22.     cin.tie(0);
  23.     cout.tie(0);
  24.  
  25.     // Ввод/вывод из файла
  26.     freopen("input.txt", "r", stdin);
  27.     freopen("output.txt", "w", stdout);
  28.  
  29.     // Ввод
  30.     int n;
  31.     cin >> n;
  32.     int prev, cur;
  33.     cin >> prev;
  34.     long long hash_a[n];
  35.     hash_a[0] = 0;
  36.     for(int i = 1; i < n; i++)
  37.     {
  38.         cin >> cur;
  39.         hash_a[i] = (hash_a[i - 1] + ((cur - prev + 1) * bin_pow(p1, i, p2)) % p2) % p2;
  40.         prev = cur;
  41.     }
  42.     int m;
  43.     cin >> m;
  44.     cin >> prev;
  45.     long long hash_b = 0;
  46.     for(int i = 1; i < m; i++)
  47.     {
  48.         cin >> cur;
  49.         hash_b = (hash_b + ((cur - prev + 1) * bin_pow(p1, i, p2)) % p2) % p2;
  50.         prev = cur;
  51.     }
  52.     m--, n--;
  53.     for(int i = m; i <= n; i++)
  54.     {
  55.         {
  56.             cout << i - m + 1;
  57.             exit(0);
  58.         }
  59.         hash_b = (hash_b * p1) % p2;
  60.     }
  61.  
  62.  
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement