P10479 Match Statistics

Axuan wrote two strings on paper, denoted as $A$ and $B$. Using what he learned in data structures and algorithms class, he can easily compute, for any starting position in string $A$, the matching length between the suffix substring starting from that position and string $B$. However, Axuan is a hardworking and curious student, and he asks you $Q$ questions. In each question, he gives you an integer $X$. You need to tell him how many starting positions satisfy that the matching length between the suffix substring of $A$ starting at that position and $B$ is exactly $X$. For example: $A=\text{aabcde}$, $B=\text{ab}$. Then $A$ has $6$ suffix substrings: $\text{aabcde}$, $\text{abcde}$, $\text{bcde}$, $\text{cde}$, $\text{de}$, $\text{e}$. Their matching lengths with $B=\text{ab}$ are $1,2,0,0,0,0$. Therefore, in $A$, there are $4$ positions whose matching length with $B$ is exactly $0$, $1$ position whose matching length is exactly $1$, and $1$ position whose matching length is exactly $2$.

The first line contains three integers $N, M, Q$, representing the length of string $A$, the length of string $B$, and the number of queries. The second line is string $A$, and the third line is string $B$. In the next $Q$ lines, each line contains one integer $x$, representing one query.

Output $Q$ lines. Each line is the answer to the corresponding query, in order.

Constraints: $1\leq N, M, Q, X\leq 200000$。 Translated by ChatGPT 5