P10474 [ICPC 2011 Beijing R] Matrix Matrix Hashing

Given an $M$-row $N$-column $01$ matrix, and $Q$ $01$ matrices of size $A$ rows and $B$ columns, you need to determine which of these $Q$ matrices appear in the original matrix. A $01$ matrix means that every element in the matrix is either $0$ or $1$.

The first line of the input file contains $M, N, A, B$, as described above. The next $M$ lines each contain $N$ characters, each being either $0$ or $1$, describing the original matrix. The next line contains the number of queries $Q$. Then follow $Q$ matrices, totaling $Q \times A$ lines, where each line contains $B$ characters, describing the $Q$ $01$ matrices.

Output $Q$ lines. Each line should be $0$ or $1$, indicating whether the corresponding matrix appears in the original matrix: $0$ means it does not appear, and $1$ means it does.

For $100\%$ of the actual testdata, $1 \leq M, N \leq 1000$, and $Q = 1000$. For $40\%$ of the testdata, $A = 1$. For $80\%$ of the testdata, $A \leq 10$. For $100\%$ of the testdata, $A \leq 100$. Translated by ChatGPT 5