Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const long long p1 = 149;
  8. const long long p2 = 503;
  9. const long long mod = 1010001023;
  10.  
  11. int n, m, a, b;
  12. vector<vector<char>> costr, lksh;
  13. vector<vector<long long>> hsh_costr, hsh_lksh;
  14. vector<long long> pow1, pow2;
  15.  
  16. void fill_hsh() {
  17.     for (int i = 1; i <= n; ++i) {
  18.         for (int j = 1; j <= m; ++j) {
  19.             hsh_costr[i][j] = (hsh_costr[i - 1][j] * p1 -
  20.                     hsh_costr[i - 1][j - 1] * p1 * p2 +
  21.                     hsh_costr[i][j - 1] * p2 + costr[i][j]) % mod;
  22.         }
  23.     }
  24.  
  25.     for (int i = 1; i <= a; ++i) {
  26.         for (int j = 1; j <= b; ++j) {
  27.             hsh_lksh[i][j] = (hsh_lksh[i - 1][j] * p1 -
  28.                     hsh_lksh[i - 1][j - 1] * p1 * p2 +
  29.                     hsh_lksh[i][j - 1] * p2 + lksh[i][j]) % mod;
  30.         }
  31.     }
  32. }
  33.  
  34. void fill_power() {
  35.     pow1[0] = 1;
  36.     for (int i = 1; i <= n; ++i) {
  37.         pow1[i] = (pow1[i - 1] * p1) % mod;
  38.     }
  39.  
  40.     pow2[0] = 1;
  41.     for (int i = 1; i <= n; ++i) {
  42.         pow1[i] = (pow2[i - 1] * p2) % mod;
  43.     }
  44. }
  45.  
  46. long long get_subhash_costr(int i, int j, int w, int h) {
  47.     long long ans = hsh_costr[i][j] -
  48.             (hsh_costr[i - w][j] * pow1[w]) % mod +
  49.             (((hsh_costr[i - w][j - h] * pow1[w]) % mod) * pow2[h]) % mod -
  50.             (hsh_costr[i][j - h] * pow2[h]) % mod;
  51.     if (ans < 0) {
  52.         ans += mod;
  53.     }
  54.     return ans;
  55. }
  56.  
  57. long long get_subhash_lksh(int i, int j, int w, int h) {
  58.     long long ans = hsh_lksh[i][j] -
  59.             (hsh_lksh[i - w][j] * pow1[w]) % mod +
  60.             (((hsh_lksh[i - w][j - h] * pow1[w]) % mod) * pow2[h]) % mod -
  61.             (hsh_lksh[i][j - h] * pow2[h]) % mod;
  62.     if (ans < 0) {
  63.         ans += mod;
  64.     }
  65.     return ans;
  66. }
  67.  
  68. bool can(int x1, int y1, int x2, int y2) {
  69.     int l1 = 0, r1 = a + 1, mid;
  70.     while (l1 < r1 - 1) {
  71.         mid = l1 + (r1 - l1) / 2;
  72.         if (get_subhash_costr(x1 + mid, y2, mid, b) ==
  73.             hsh_lksh[mid][b]) {
  74.             l1 = mid;
  75.         } else {
  76.             r1 = mid;
  77.         }
  78.     }
  79.  
  80.     if (l1 == a) {
  81.         return true;
  82.     }
  83.  
  84.     int l2 = 0, r2 = b + 1;
  85.     while (l2 < r2 - 1) {
  86.         mid = l2 + (r2 - l2) / 2;
  87.         if (get_subhash_costr(x2, y1 + mid, a, mid) ==
  88.             hsh_lksh[b][mid]) {
  89.             l2 = mid;
  90.         } else {
  91.             r2 = mid;
  92.         }
  93.     }
  94.  
  95.     if (l1 < a - 1) {
  96.         if (get_subhash_costr(x2, y2, a - l1 - 1, b) !=
  97.             get_subhash_lksh(a, b, a - l1 - 1, b)) {
  98.             return false;
  99.         }
  100.     }
  101.     if (l2 < b - 1) {
  102.         if (get_subhash_costr(x2, y2, a, b - l1 - 1) !=
  103.             get_subhash_lksh(a, b, a, b - l1 - 1)) {
  104.             return false;
  105.         }
  106.     }
  107. }
  108.  
  109. int main() {
  110.     cin >> n >> m;
  111.     costr.resize(n + 1, vector<char> (m + 1));
  112.     hsh_costr.resize(n + 1, vector<long long> (m + 1));
  113.     for (int i = 1; i <= n; ++i) {
  114.         for (int j = 1; j <= m; ++j) {
  115.             cin >> costr[i][j];
  116.         }
  117.     }
  118.     cin >> a >> b;
  119.     lksh.resize(a + 1, vector<char> (b + 1));
  120.     hsh_lksh.resize(a + 1, vector<long long> (b + 1));
  121.     for (int i = 1; i <= a; ++i) {
  122.         for (int j = 1; j <= b; ++j) {
  123.             cin >> lksh[i][j];
  124.         }
  125.     }
  126.  
  127.     pow1.resize(n + 1);
  128.     pow2.resize(m + 1);
  129.  
  130.     fill_power();
  131.     fill_hsh();
  132.  
  133.     for (auto i : hsh_lksh) {
  134.         for (auto j : i) {
  135.             cout << j << " ";
  136.         }
  137.         cout << "\n";
  138.     }
  139.     cout << "\n";
  140.     for (auto i : hsh_costr) {
  141.         for (auto j : i) {
  142.             cout << j << " ";
  143.         }
  144.         cout << "\n";
  145.     }
  146.  
  147.     int ans = 0;
  148.     for (int i = a; i <= n; ++i) {
  149.         for (int j = b; j <= m; ++j) {
  150.             ans += can(i - a + 1, j - b + 1, i, j);
  151.         }
  152.     }
  153.     cout << ans << "\n";
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement