Comet OJ

C0944 [HAOI2017]字符串

内存限制：256 MB 时间限制：1000 ms

题目描述

给出一个字符串 $s$ 和 $n$个字符串 $p_i$，求每个字符串 $p_i$ 在 $s$ 中出现的次数。注意这里两个字符串相等的定义稍作改变。

给定一个常数 $k$，对于两个字符串 $a, b$，如果 $a = b$，那么满足：

  1. $|a| = |b|$；
  2. 对于所有 $a_i \neq b_i$ 以及 $a_j \neq b_j$，满足 $|i-j| < k$。

如果 $|a| = |b| \le k$，那么认为 $a = b$。

输入格式

第一行一个整数 $k$。

第二行一个字符串 $s$。

第三行一个整数 $n$，接下来 $n$ 行每行一个字符串表示 $p_i$。

所有的字符 ASCII 码在 $33$ 至 $126$ 之间。

输出

输出 $n$ 行，表示每个 $p_i$ 在 $s$ 中出现的次数。

样例

样例输入 1

1
xyz
3
xz
y
xzy

样例输出 1

2
3
0

提示

【样例解释】

对于 $p_1$，$xz = xy, xz = yz$，因为都只有一个位置差异。

对于 $p_2$，$y = x, y = y, y = z$，同理。

对于 $p_3$，$xzy \neq xyz$，最大差 $= 1$ 不满足 $< k = 1$。

【数据范围】

对于 $20\%$ 的数据，$|s|, \sum |p_i| \le 10^3$；

对于另外 $20\%$ 的数据，$n \le 100$；

对于另外 $20\%$ 的数据，$|s|, \sum |p_i| \le 5 \cdot 10^4$；

对于 $100\%$ 的数据，$|s|, \sum |p_i| \le 2 \cdot 10^5$。