Advertisement
cosenza987

Untitled

May 9th, 2022
730
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. //Слава Україні, Героям слава 🇺🇦
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. using ull = unsigned long long;
  8.  
  9. const int N = 2e3 + 7;
  10.  
  11. ull h[N][N], p[2][N];
  12. ull px = 3731, py = 2999;
  13. int x, y, n, m;
  14.  
  15. void build(vector<string> &v, int a, int b) {
  16.     p[0][0] = 1;
  17.     p[1][0] = 1;
  18.     for(int i = 1; i <= a; i++) {
  19.         p[0][i] = p[0][i - 1] * px;
  20.     }
  21.     for(int i = 1; i <= b; i++) {
  22.         p[1][i] = p[1][i - 1] * py;
  23.     }
  24.     for(int i = 0; i < a; i++) {
  25.         for(int j = 0; j < b; j++) {
  26.             h[i + 1][j + 1] = (v[i][j] == 'x' ? 2 : 1);
  27.         }
  28.     }
  29.     for(int i = 0; i <= a; i++) {
  30.         for(int j = 0; j < b; j++) {
  31.             h[i][j + 1] = h[i][j + 1] + h[i][j] * py;
  32.         }
  33.     }
  34.     for(int i = 0; i < a; i++) {
  35.         for(int j = 0; j <= b; j++) {
  36.             h[i + 1][j] = h[i + 1][j] + h[i][j] * px;
  37.         }
  38.     }
  39. }
  40.  
  41. ull fhash(int x1, int y1, int x2, int y2) {
  42.     x1--; y1--;
  43.     int dx = x2 - x1, dy = y2 - y1;
  44.     return (h[x2][y2] - h[x2][y1] * p[1][dy]) - (h[x1][y2] - h[x1][y1] * p[1][dy]) * p[0][dx];
  45. }
  46.  
  47. int main() {
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(0);
  50.     cin >> x >> y >> n >> m;
  51.     vector<string> a(x), v(n);
  52.     for(int i = 0; i < x; i++) {
  53.         cin >> a[i];
  54.     }
  55.     for(int i = 0; i < n; i++) {
  56.         cin >> v[i];
  57.     }
  58.     build(a, x, y);
  59.     ull ref = fhash(1, 1, x, y);
  60.     memset(h, 0, sizeof(h));
  61.     build(v, n, m);
  62.     int ans = 0;
  63.     for(int i = 1; i <= n; i++) {
  64.         for(int j = 1; j <= m; j++) {
  65.             if(i + x - 1 <= n and j + y - 1 <= m) {
  66.                 if(fhash(i, j, i + x - 1, j + y - 1) == ref) {
  67.                     ans++;
  68.                 }
  69.             }
  70.         }
  71.     }
  72.     cout << ans << "\n";
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement