• API
• FAQ
• Tools
• Archive
daily pastebin goal
17%
SHARE
TWEET

# Untitled

a guest Dec 15th, 2018 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top