Advertisement
Manioc

2d_hash

Jul 15th, 2018
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 1007
  3.  
  4. using namespace std;
  5. typedef long long ll;
  6.  
  7. ll all[MAX][MAX], peace[MAX], power, inv[MAX];
  8. ll base[3] = {1000007, 317, 307};
  9. ll mod[3] = {1000000007, 104000717, 104000711};
  10. char str[MAX];
  11.  
  12. int n, m, x, y;
  13. //ll inverse(int a, int b, int s0 = 1, int s1 = 0){
  14. //    return b == 0 ? s0: inverse(b, a%b, s1, s0 - s1*(a/b));
  15. //}
  16.  
  17. void lineHash(int id, int l, int flag){
  18.     ll hash = 0;
  19.     for(int i = 1; i <= l; i++){
  20.         hash = (hash*1ll*base[0] + str[i])%mod[0];
  21.         if(!flag) all[id][i] = hash;
  22.     }
  23.     if(flag) peace[id] = hash;
  24. }
  25.  
  26. bool ok(int i,int j,int k){
  27.     ll res1 = (all[i][j+y-1]-all[i][j-1]*power%mod[0]+mod[0])%mod[0];
  28.     ll res2 = peace[k];
  29.     return res1 == res2;
  30. }
  31.  
  32. void debug_grid(ll arr[][MAX], int x, int y){
  33.     for(int i = 0; i <= x; i++){
  34.         for(int j = 0; j <= y; j++) cout << arr[i][j] << " ";
  35.         cout << endl;
  36.     }
  37. }
  38.  
  39. ll pow(ll a,ll b){
  40.     ll ans = 1;
  41.     while(b){
  42.         if(b&1) ans=(ans*a)%mod[0];
  43.         a = (a*a)%mod[0];
  44.         b>>=1;
  45.     }
  46.     return ans;
  47. }
  48. int main(){
  49.     int cases; scanf("%d", &cases);
  50.     while(cases--){
  51.         scanf("%d %d", &n, &m);
  52.         for(int i = 1; i <= n; i++){
  53.             scanf("%s", str+1); lineHash(i, m, 0);
  54.         }
  55.  
  56.         scanf("%d %d", &x, &y);
  57.         for(int i = 1; i <= x; i++){
  58.             scanf("%s", str+1); lineHash(i, y, 1);
  59.         }
  60.  
  61.         power = pow(base[0],y);
  62.         //debug_grid(all, n, m);
  63.         //for(int i = 1; i <= x; i++) cout << peace[i] << " ";
  64.         //cout << endl;
  65.         int ans = 0;
  66.         for(int i = 1; i <= n; i++){
  67.             if(i+x-1 > n) break;
  68.             for(int j = 1; j <= m; j++){
  69.                 if(j+y-1 > m) break;
  70.                 int k;
  71.                 for(k = i; k < i+x; k++){
  72.                    if(!ok(k,j,k-i+1)) break;
  73.                 }
  74.                 if(k >= i+x) ans++;
  75.             }
  76.         }
  77.         printf("%d\n", ans);
  78.     }
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement