Description

给定一个M行N列的01矩阵，以及Q个A行B列的01矩阵，你需要求出这Q个矩阵哪些在原矩阵中出现过。
所谓01矩阵，就是矩阵中所有元素不是0就是1。

Input

输入文件的第一行为M、N、A、B，参见题目描述。
接下来M行，每行N个字符，非0即1，描述原矩阵。
接下来一行为你要处理的询问数Q。
接下来Q个矩阵，一共Q*A行，每行B个字符，描述Q个01矩阵。

Output

你需要输出Q行，每行为0或者1，表示这个矩阵是否出现过，0表示没有出现过，1表示出现过。

Sample Input

3 3 2 2

111

000

111

3

11

00

11

11

00

11

Sample Output

1

0

1

HINT

对于100%的实际测试数据，M、N ≤ 1000，Q = 1000

对于40%的数据，A = 1。

对于80%的数据，A ≤ 10。

对于100%的数据，A ≤ 100。

solution：hash

/**************************************************************Problem: 2351User: VenishelLanguage: C++Result: AcceptedTime:2016 msMemory:17540 kb ****************************************************************/#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; 
#define N 1010
#define P 77171
#define bs1 9804799
#define bs2 9983543int n, m, A, B, Q, top;
unsigned int Hash;
unsigned int a[N][N], b[N][N], pw1[N], pw2[N];
int hash[P]; struct L{ unsigned int num;  L *nxt;  } s[N*N];void insert_hash( unsigned int x ){int t = x % P;s[++top].num = x; s[top].nxt = &s[ hash[t] ]; hash[t] = top;
}bool find( unsigned int x ){int t = x % P;for ( L *i = &s[ hash[t] ]; i; i = i->nxt )if ( i->num == x ) return true;return false; 
}int main(){top = 0;scanf( "%d%d%d%d", &m, &n, &A, &B );pw1[0] = pw2[0] = 1;for ( int i = 1; i <= m; i++ ) for ( int j = 1; j <= n; j++ ) scanf( "%1d", &a[i][j]);for ( int i = 1; i <= max(m,n); i++ ) pw1[i] = pw1[i-1]*bs1, pw2[i] = pw2[i-1]*bs2;for ( int i = 1; i <= m; i++ ) for ( int j = 1; j <= n; j++ ) a[i][j] += a[i-1][j]*bs1;for ( int i = 1; i <= m; i++)  for ( int j = 1; j <= n; j++ ) a[i][j] += a[i][j-1]*bs2;for ( int i = A; i <= m; i++)for ( int j = B; j <= n; j++){Hash = a[i][j]; Hash -= a[i-A][j]*pw1[A]; Hash -= a[i][j-B]*pw2[B];Hash += a[i-A][j-B]*pw1[A]*pw2[B];insert_hash( Hash );}scanf( "%d", &Q );while ( Q-- ){for ( int i = 1; i <= A; i++) for ( int j = 1; j <= B; j++ ) scanf( "%1d", &b[i][j]);for ( int i = 1; i <= A; i++)for ( int j = 1; j <= B; j++ ) b[i][j] += b[i-1][j] * bs1;for ( int i = 1; i <= A; i++ ) for ( int j = 1; j <= B; j++ ) b[i][j] += b[i][j-1] * bs2;printf( "%d\n", find( b[A][B]) ? 1 : 0 );}  return 0;
}