Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- const long long p1 = 149;
- const long long p2 = 503;
- const long long mod = 1010001023;
- int n, m, a, b;
- vector<vector<char>> costr, lksh;
- vector<vector<long long>> hsh_costr, hsh_lksh;
- vector<long long> pow1, pow2;
- void fill_hsh() {
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- hsh_costr[i][j] = (hsh_costr[i - 1][j] * p1 -
- hsh_costr[i - 1][j - 1] * p1 * p2 +
- hsh_costr[i][j - 1] * p2 + costr[i][j]) % mod;
- }
- }
- for (int i = 1; i <= a; ++i) {
- for (int j = 1; j <= b; ++j) {
- hsh_lksh[i][j] = (hsh_lksh[i - 1][j] * p1 -
- hsh_lksh[i - 1][j - 1] * p1 * p2 +
- hsh_lksh[i][j - 1] * p2 + lksh[i][j]) % mod;
- }
- }
- }
- void fill_power() {
- pow1[0] = 1;
- for (int i = 1; i <= n; ++i) {
- pow1[i] = (pow1[i - 1] * p1) % mod;
- }
- pow2[0] = 1;
- for (int i = 1; i <= n; ++i) {
- pow1[i] = (pow2[i - 1] * p2) % mod;
- }
- }
- long long get_subhash_costr(int i, int j, int w, int h) {
- long long ans = hsh_costr[i][j] -
- (hsh_costr[i - w][j] * pow1[w]) % mod +
- (((hsh_costr[i - w][j - h] * pow1[w]) % mod) * pow2[h]) % mod -
- (hsh_costr[i][j - h] * pow2[h]) % mod;
- if (ans < 0) {
- ans += mod;
- }
- return ans;
- }
- long long get_subhash_lksh(int i, int j, int w, int h) {
- long long ans = hsh_lksh[i][j] -
- (hsh_lksh[i - w][j] * pow1[w]) % mod +
- (((hsh_lksh[i - w][j - h] * pow1[w]) % mod) * pow2[h]) % mod -
- (hsh_lksh[i][j - h] * pow2[h]) % mod;
- if (ans < 0) {
- ans += mod;
- }
- return ans;
- }
- bool can(int x1, int y1, int x2, int y2) {
- int l1 = 0, r1 = a + 1, mid;
- while (l1 < r1 - 1) {
- mid = l1 + (r1 - l1) / 2;
- if (get_subhash_costr(x1 + mid, y2, mid, b) ==
- hsh_lksh[mid][b]) {
- l1 = mid;
- } else {
- r1 = mid;
- }
- }
- if (l1 == a) {
- return true;
- }
- int l2 = 0, r2 = b + 1;
- while (l2 < r2 - 1) {
- mid = l2 + (r2 - l2) / 2;
- if (get_subhash_costr(x2, y1 + mid, a, mid) ==
- hsh_lksh[b][mid]) {
- l2 = mid;
- } else {
- r2 = mid;
- }
- }
- if (l1 < a - 1) {
- if (get_subhash_costr(x2, y2, a - l1 - 1, b) !=
- get_subhash_lksh(a, b, a - l1 - 1, b)) {
- return false;
- }
- }
- if (l2 < b - 1) {
- if (get_subhash_costr(x2, y2, a, b - l1 - 1) !=
- get_subhash_lksh(a, b, a, b - l1 - 1)) {
- return false;
- }
- }
- }
- int main() {
- cin >> n >> m;
- costr.resize(n + 1, vector<char> (m + 1));
- hsh_costr.resize(n + 1, vector<long long> (m + 1));
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- cin >> costr[i][j];
- }
- }
- cin >> a >> b;
- lksh.resize(a + 1, vector<char> (b + 1));
- hsh_lksh.resize(a + 1, vector<long long> (b + 1));
- for (int i = 1; i <= a; ++i) {
- for (int j = 1; j <= b; ++j) {
- cin >> lksh[i][j];
- }
- }
- pow1.resize(n + 1);
- pow2.resize(m + 1);
- fill_power();
- fill_hsh();
- for (auto i : hsh_lksh) {
- for (auto j : i) {
- cout << j << " ";
- }
- cout << "\n";
- }
- cout << "\n";
- for (auto i : hsh_costr) {
- for (auto j : i) {
- cout << j << " ";
- }
- cout << "\n";
- }
- int ans = 0;
- for (int i = a; i <= n; ++i) {
- for (int j = b; j <= m; ++j) {
- ans += can(i - a + 1, j - b + 1, i, j);
- }
- }
- cout << ans << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement