题目链接：

题意：给出一个n*m的01矩阵。再给出10个A*B的小01矩阵。判断这些小的矩阵是不是原矩阵的子矩阵。

思路：将原矩阵的每个A*B的矩阵哈希成一个值。给出的小矩阵也哈希成一个值。则直接查找即可。

 

char s[N][N];

int n,m,A,B;

u64 h[N][N],f[N][N];

u64 p[N];

void init()

{

    if(B>m) return;

    int i,j;

    u64 x;

    FOR1(i,n)

    {

        x=0;

        FOR1(j,B) x=x*107+s[i][j];

        f[i][B]=x;

        for(j=B+1;j<=m;j++) 

        {

            f[i][j]=(f[i][j-1]-s[i][j-B]*p[B-1])*107+s[i][j];

        }

    }

    if(n<A) return;

    for(j=B;j<=m;j++)

    {

        x=0;

        FOR1(i,A) x=x*107+f[i][j];

        h[A][j]=x;

        for(i=A+1;i<=n;i++) 

        {

            h[i][j]=(h[i-1][j]-f[i-A][j]*p[A-1])*107+f[i][j];

        }

    }

}

char str[N][N];

int OK(int x,int y)

{

    int i,j;

    FOR1(i,A) FOR1(j,B) if(str[i][j]!=s[x-A+i][y-B+j])

    {

        return 0;

    }

    return 1;

}

int check()

{

    if(B>m||A>n) return 0;

    int i,j;

    u64 a[105];

    FOR1(i,A)

    {

        a[i]=0;

        FOR1(j,B) a[i]=a[i]*107+str[i][j];

    }

    i64 x=0;

    FOR1(i,A) x=x*107+a[i];

    for(i=A;i<=n;i++) for(j=B;j<=m;j++) 

    {

        if(h[i][j]==x&&OK(i,j)) return 1;

    }

    return 0;

}

int main()

{

    RD(n,m); RD(A,B);

    int i;

    FOR1(i,n) RD(s[i]+1);

    p[0]=1;

    for(i=1;i<N;i++) p[i]=p[i-1]*107;

    init();

    int k;

    RD(k);

    while(k--)

    {

        FOR1(i,A) RD(str[i]+1);

        PR(check());

    }

}