Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- long long p1 = 31;
- long long p2 = 239;
- long long mod1 = 1125060217;
- long long mod2 = 1500000233;
- char c1[1001][1001];
- char c2[1001][1001];
- int n1, m1, n2, m2;
- vector<long long> h;
- long long b1[1001][1001];
- long long b2[1001][1001];
- void compare_push(long long x, long long y) {
- long long ans = x;
- ans = (ans << 31) + y;
- h.push_back(ans);
- }
- long long fast_st(long long x, long long p, long long mod) {
- if (p == 0) {
- return 1;
- }
- if (p % 2 == 0) {
- long long y = fast_st(x, p / 2, mod);
- return (y * y) % mod;
- }
- return (fast_st(x, p - 1, mod) * x) % mod;
- }
- vector<vector <long long> > st(9, vector<long long> (1001));
- void make_st(vector<long long>& vec, long long p, long long mod) {
- vec[0] = 1;
- for (int i = 1; i <= 1000; ++i) {
- vec[i] = vec[i - 1] * p % mod;
- }
- }
- void make_result_st() {
- long long rp1_1 = fast_st(p1, mod1 - 2, mod1);
- long long rp2_1 = fast_st(p2, mod1 - 2, mod1);
- long long rp1_2 = fast_st(p1, mod2 - 2, mod2);
- long long rp2_2 = fast_st(p2, mod2 - 2, mod2);
- make_st(st[1], p1, mod1);
- make_st(st[2], rp1_1, mod1);
- make_st(st[3], p2, mod1);
- make_st(st[4], rp2_1, mod1);
- make_st(st[5], p1, mod2);
- make_st(st[6], rp1_2, mod2);
- make_st(st[7], p2, mod2);
- make_st(st[8], rp2_2, mod2);
- }
- void make_hash() {
- for (int i = 1; i <= n1; ++i) {
- for (int j = 1; j <= m1; ++j) {
- b1[i][j] = (mod1 + b1[i - 1][j] + b1[i][j - 1] - b1[i - 1][j - 1] +
- ((st[1][i] * st[3][j]) % mod1) * (long long)(c1[i][j] - 'a' + 1)) % mod1;
- }
- }
- for (int i = 1; i <= n1; ++i) {
- for (int j = 1; j <= m1; ++j) {
- b2[i][j] = (mod2 + b2[i - 1][j] + b2[i][j - 1] - b2[i - 1][j - 1] +
- ((st[5][i] * st[7][j]) % mod2) * (long long)(c1[i][j] - 'a' + 1)) % mod2;
- }
- }
- long long ans1 = 0;
- long long ans2 = 0;
- for (int i = 1; i <= n2; ++i) {
- for (int j = 1; j <= m2; ++j) {
- ans1 = (ans1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c2[i][j] - 'a' + 1)) % mod1;
- ans2 = (ans2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c2[i][j] - 'a' + 1)) % mod2;
- }
- }
- for (int i = 1; i <= n2; ++i) {
- for (int j = 1; j <= m2; ++j) {
- long long ans_1 = ans1;
- long long ans_2 = ans2;
- ans_1 = (ans_1 + mod1 - ((st[1][i] * st[3][j]) % mod1) *(long long)(c2[i][j] - 'a' + 1) % mod1) % mod1;
- ans_2 = (ans_2 + mod2 - ((st[5][i] * st[7][j]) % mod2) *(long long)(c2[i][j] - 'a' + 1) % mod2) % mod2;
- for (char c = 'a'; c <= 'z'; ++c) {
- compare_push((ans_1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c - 'a' + 1)) % mod1,
- (ans_2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c - 'a' + 1)) % mod2);
- //cout << "c " << c << " " << ans_1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c - 'a' + 1) % mod1 <<
- //" " << ans_2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c - 'a' + 1) % mod2 << endl;
- }
- }
- }
- h.erase(unique(h.begin(), h.end()), h.end());
- }
- int main() {
- freopen("find-lksh.in", "r", stdin);
- freopen("find-lksh.out", "w", stdout);
- cin >> n1 >> m1;
- for (int i = 1; i <= n1; ++i) {
- for (int j = 1; j <= m1; ++j) {
- cin >> c1[i][j];
- }
- }
- cin >> n2 >> m2;
- for (int i = 1; i <= n2; ++i) {
- for (int j = 1; j <= m2; ++j) {
- cin >> c2[i][j];
- }
- }
- make_result_st();
- make_hash();
- int ans = 0;
- sort(h.begin(), h.end());
- for (int i = 1; i <= n1 - n2 + 1; ++i) {
- for (int j = 1; j <= m1 - m2 + 1; ++j) {
- long long x1 = (mod1 * 2 + b1[i + n2 - 1][j + m2 - 1] - b1[i - 1][j + m2 - 1] - b1[i + n2 - 1][j - 1] + b1[i - 1][j - 1]) % mod1;
- long long x2 = (mod2 * 2 + b2[i + n2 - 1][j + m2 - 1] - b2[i - 1][j + m2 - 1] - b2[i + n2 - 1][j - 1] + b2[i - 1][j - 1]) % mod2;
- x1 = (((x1 * st[2][i - 1]) % mod1) * st[4][j - 1]) % mod1;
- x2 = (((x2 * st[6][i - 1]) % mod2) * st[8][j - 1]) % mod2;
- long long x = (x1 << 31) + x2;
- if (binary_search(h.begin(), h.end(), x)) {
- ++ans;
- }
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement