problem

二维hash模版题，code：

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int maxn=1e3+5;
const int b1=131;
const int b2=137;
int n,m,x,y,ans;
ull p1[maxn],p2[maxn],ha[maxn][maxn],hb[maxn][maxn];
ull get(ull h[][maxn],int x1,int y1,int x2,int y2){
    return h[x2][y2]
         -h[x1-1][y2]*p1[x2-x1+1]
         -h[x2][y1-1]*p2[y2-y1+1]
         +h[x1-1][y1-1]*p1[x2-x1+1]*p2[y2-y1+1];
}
int main(){
    p1[0]=p2[0]=0;
    for(int i=1;i<maxn;i++){
        p1[i]=p1[i-1]*b1;
        p2[i]=p2[i-1]*b2;
    }
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                char ch;
                cin>>ch;
                ha[i][j]=ch+ha[i-1][j]*b1+ha[i][j-1]*b2-ha[i-1][j-1]*b1*b2;
            }
        }
        cin>>x>>y;
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                char ch;
                cin>>ch;
                hb[i][j]=hb[i-1][j]*b1+hb[i][j-1]*b2-hb[i-1][j-1]*b1*b2+ch;
            }
        }
        ans=0;
        for(int i=1;i<=n-x+1;i++){
            for(int j=1;j<=m-y+1;j++){
                if(hb[x][y]==get(ha,i,j,i+x-1,j+y-1)) ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}