Problem Description

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$.

Input Format

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 Format

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

6 2 5
aabcde
ab
0
1
2
3
4

4
1
1
0
0

Hint

Constraints: $1\leq N, M, Q, X\leq 200000$。

Translated by ChatGPT 5