C++ 代码

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
#include<assert.h>
#include<unordered_set>
using namespace std;

const int N=1e6+10;
using ll=unsigned long long;
ll hhash[1001][1001];
ll ppow[N];
ll col[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int m,n;
    cin>>m>>n;
    int a,b;
    cin>>a>>b;

    int i,j;
    char c;

    //先对每一行进行哈希
    //前两次取2进制,结果被爆
    ppow[0]=1;
    for(i=1;i<=m;++i)
    {
        hhash[i][0]=0;
        for(j=1;j<=n;++j)
        {
            int t=(i-1)*n+j;
            ppow[t]=ppow[t-1]*131;
            cin>>c;
            hhash[i][j]=hhash[i][j-1]*131+(c-'0');
        }
    }

    //存储所有的a*b的矩阵的哈希值
    unordered_set<ll> up;
    for(j=1;j<=n-b+1;++j)
    {
        //对每一列做哈希
        for(i=1;i<=m;++i)
        {
            col[i]=col[i-1]*ppow[b]+hhash[i][j+b-1]-hhash[i][j-1]*ppow[b];
        }
        for(i=1;i<=m-a+1;++i)
            up.insert(col[i+a-1]-col[i-1]*ppow[a*b]);

    }

    int q;
    cin>>q;
    int k;
    for(k=0;k<q;++k)
    {
        ll hv=0;
        for(i=0;i<a;++i)
        {
            for(j=0;j<b;++j)
            {
                cin>>c;
                hv=hv*131+(c-'0');
            }
        }

        if(up.find(hv)!=up.end())cout<<1<<endl;
        else cout<<0<<endl;
    }

    return 0;


}