Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 1007
- using namespace std;
- typedef long long ll;
- ll all[MAX][MAX], peace[MAX], power, inv[MAX];
- ll base[3] = {1000007, 317, 307};
- ll mod[3] = {1000000007, 104000717, 104000711};
- char str[MAX];
- int n, m, x, y;
- //ll inverse(int a, int b, int s0 = 1, int s1 = 0){
- // return b == 0 ? s0: inverse(b, a%b, s1, s0 - s1*(a/b));
- //}
- void lineHash(int id, int l, int flag){
- ll hash = 0;
- for(int i = 1; i <= l; i++){
- hash = (hash*1ll*base[0] + str[i])%mod[0];
- if(!flag) all[id][i] = hash;
- }
- if(flag) peace[id] = hash;
- }
- bool ok(int i,int j,int k){
- ll res1 = (all[i][j+y-1]-all[i][j-1]*power%mod[0]+mod[0])%mod[0];
- ll res2 = peace[k];
- return res1 == res2;
- }
- void debug_grid(ll arr[][MAX], int x, int y){
- for(int i = 0; i <= x; i++){
- for(int j = 0; j <= y; j++) cout << arr[i][j] << " ";
- cout << endl;
- }
- }
- ll pow(ll a,ll b){
- ll ans = 1;
- while(b){
- if(b&1) ans=(ans*a)%mod[0];
- a = (a*a)%mod[0];
- b>>=1;
- }
- return ans;
- }
- int main(){
- int cases; scanf("%d", &cases);
- while(cases--){
- scanf("%d %d", &n, &m);
- for(int i = 1; i <= n; i++){
- scanf("%s", str+1); lineHash(i, m, 0);
- }
- scanf("%d %d", &x, &y);
- for(int i = 1; i <= x; i++){
- scanf("%s", str+1); lineHash(i, y, 1);
- }
- power = pow(base[0],y);
- //debug_grid(all, n, m);
- //for(int i = 1; i <= x; i++) cout << peace[i] << " ";
- //cout << endl;
- int ans = 0;
- for(int i = 1; i <= n; i++){
- if(i+x-1 > n) break;
- for(int j = 1; j <= m; j++){
- if(j+y-1 > m) break;
- int k;
- for(k = i; k < i+x; k++){
- if(!ok(k,j,k-i+1)) break;
- }
- if(k >= i+x) ans++;
- }
- }
- printf("%d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement