核心点:不要担心Java溢出称为负数的情况,因为只做乘法而不做除法的溢出时不用担心的。
import java.util.*;
import java.io.*;
public class Main{
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static long[][] h;
static long[] pow;
static long P = 131;
static HashSet<Long> set = new HashSet<>();
public static void main(String[] args) throws IOException {
String[] fl = bf.readLine().split(" ");
int M = Integer.parseInt(fl[0]);int N = Integer.parseInt(fl[1]);
int A = Integer.parseInt(fl[2]);int B = Integer.parseInt(fl[3]);
h = new long[M+1][N+1];pow = new long[A*B+1];pow[0] = 1;
for (int i = 1; i <= A * B ; i++) pow[i] = pow[i-1] * P;
for (int i = 1; i <= M; i++) {
char[] chars = bf.readLine().toCharArray();
for (int j = 1; j <= N; j++) {
h[i][j] = h[i][j-1] * P + chars[j-1] - '0';
}
}
for (int j = B; j <= N ; j++) {
int l = j - B + 1;
int r = j;
long val = 0;
for (int i = 1; i <= M ; i++) {
val = val * pow[B] + (h[i][r] - h[i][l-1] * pow[B]);
if (i > A){
//删掉最前面那一层
val = val - (h[i-A][r] - h[i-A][l-1] * pow[B]) * pow[A*B];
}
if (i >= A){
set.add(val);
}
}
}
int Q = Integer.parseInt(bf.readLine());
for (int k = 0; k < Q; k++) {
long curVal = 0;
for (int i = 0; i < A; i++) {
char[] chars = bf.readLine().toCharArray();
for (int j = 0; j < B; j++) {
curVal = curVal * P + chars[j] - '0';
}
}
if (set.contains(curVal)){
bw.write("1\n");
}else {
bw.write("0\n");
}
}
bw.flush();
}
}