Advertisement
Guest User

Untitled

a guest
Dec 17th, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.40 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long p1 = 31;
  4. long long p2 = 239;
  5. long long mod1 = 1125060217;
  6. long long mod2 = 1500000233;
  7. char c1[1001][1001];
  8. char c2[1001][1001];
  9. int n1, m1, n2, m2;
  10.  
  11. vector<long long> h;
  12. long long b1[1001][1001];
  13. long long b2[1001][1001];
  14.  
  15. void compare_push(long long x, long long y) {
  16.     long long ans = x;
  17.     ans = (ans << 31) + y;
  18.     h.push_back(ans);
  19. }
  20.  
  21. long long fast_st(long long x, long long p, long long mod) {
  22.     if (p == 0) {
  23.         return 1;
  24.     }
  25.     if (p % 2 == 0) {
  26.         long long y = fast_st(x, p / 2, mod);
  27.         return (y * y) % mod;
  28.     }
  29.     return (fast_st(x, p - 1, mod) * x) % mod;
  30. }
  31. vector<vector <long long> > st(9, vector<long long> (1001));
  32.  
  33. void make_st(vector<long long>& vec, long long p, long long mod) {
  34.     vec[0] = 1;
  35.     for (int i = 1; i <= 1000; ++i) {
  36.         vec[i] = vec[i - 1] * p % mod;
  37.     }
  38. }
  39. void make_result_st() {
  40.     long long rp1_1 = fast_st(p1, mod1 - 2, mod1);
  41.     long long rp2_1 = fast_st(p2, mod1 - 2, mod1);
  42.     long long rp1_2 = fast_st(p1, mod2 - 2, mod2);
  43.     long long rp2_2 = fast_st(p2, mod2 - 2, mod2);
  44.     make_st(st[1], p1, mod1);
  45.     make_st(st[2], rp1_1, mod1);
  46.     make_st(st[3], p2, mod1);
  47.     make_st(st[4], rp2_1, mod1);
  48.     make_st(st[5], p1, mod2);
  49.     make_st(st[6], rp1_2, mod2);
  50.     make_st(st[7], p2, mod2);
  51.     make_st(st[8], rp2_2, mod2);
  52. }
  53. void make_hash() {
  54.     for (int i = 1; i <= n1; ++i) {
  55.         for (int j = 1; j <= m1; ++j) {
  56.             b1[i][j] = (mod1 + b1[i - 1][j] + b1[i][j - 1] - b1[i - 1][j - 1] +
  57.                         ((st[1][i] * st[3][j]) % mod1) * (long long)(c1[i][j] - 'a' + 1)) % mod1;
  58.         }
  59.     }
  60.     for (int i = 1; i <= n1; ++i) {
  61.         for (int j = 1; j <= m1; ++j) {
  62.             b2[i][j] = (mod2 + b2[i - 1][j] + b2[i][j - 1] - b2[i - 1][j - 1] +
  63.                         ((st[5][i] * st[7][j]) % mod2) * (long long)(c1[i][j] - 'a' + 1)) % mod2;
  64.         }
  65.     }
  66.     long long ans1 = 0;
  67.     long long ans2 = 0;
  68.     for (int i = 1; i <= n2; ++i) {
  69.         for (int j = 1; j <= m2; ++j) {
  70.             ans1 = (ans1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c2[i][j] - 'a' + 1)) % mod1;
  71.             ans2 = (ans2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c2[i][j] - 'a' + 1)) % mod2;
  72.         }
  73.     }
  74.     for (int i = 1; i <= n2; ++i) {
  75.         for (int j = 1; j <= m2; ++j) {
  76.             long long ans_1 = ans1;
  77.             long long ans_2 = ans2;
  78.             ans_1 = (ans_1 + mod1 - ((st[1][i] * st[3][j]) % mod1) *(long long)(c2[i][j] - 'a' + 1) % mod1) % mod1;
  79.             ans_2 = (ans_2 + mod2 - ((st[5][i] * st[7][j]) % mod2) *(long long)(c2[i][j] - 'a' + 1) % mod2) % mod2;
  80.             for (char c = 'a'; c <= 'z'; ++c) {
  81.                 compare_push((ans_1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c - 'a' + 1)) % mod1,
  82.                 (ans_2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c - 'a' + 1)) % mod2);
  83.                 //cout << "c " << c << " " << ans_1 + ((st[1][i] * st[3][j]) % mod1) * (long long)(c - 'a' + 1) % mod1 <<
  84.                 //" " << ans_2 + ((st[5][i] * st[7][j]) % mod2) * (long long)(c - 'a' + 1) % mod2 << endl;
  85.             }
  86.         }
  87.     }
  88.     h.erase(unique(h.begin(), h.end()), h.end());
  89. }
  90.  
  91.  
  92. int main() {
  93.     freopen("find-lksh.in", "r", stdin);
  94.     freopen("find-lksh.out", "w", stdout);
  95.     cin >> n1 >> m1;
  96.     for (int i = 1; i <= n1; ++i) {
  97.         for (int j = 1; j <= m1; ++j) {
  98.             cin >> c1[i][j];
  99.         }
  100.     }
  101.     cin >> n2 >> m2;
  102.     for (int i = 1; i <= n2; ++i) {
  103.         for (int j = 1; j <= m2; ++j) {
  104.             cin >> c2[i][j];
  105.         }
  106.     }
  107.     make_result_st();
  108.     make_hash();
  109.     int ans = 0;
  110.     sort(h.begin(), h.end());
  111.     for (int i = 1; i <= n1 - n2 + 1; ++i) {
  112.         for (int j = 1; j <= m1 - m2 + 1; ++j) {
  113.             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;
  114.             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;
  115.             x1 = (((x1 * st[2][i - 1]) %  mod1) * st[4][j - 1]) % mod1;
  116.             x2 = (((x2 * st[6][i - 1]) %  mod2) * st[8][j - 1]) % mod2;
  117.             long long x = (x1 << 31) + x2;
  118.             if (binary_search(h.begin(), h.end(), x)) {
  119.                 ++ans;
  120.             }
  121.         }
  122.     }
  123.     cout << ans;
  124.     return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement