2673. [HAOI 2017]字符串

【题目描述】

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

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

一、$|a| = |b|$

二、对于所有 $a_i \neq b_i$ 以及 $a_j \neq b_j$，满足 $|i-j| < k$

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

【输入格式】

第一行一个整数 $k$。

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

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

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

【输出格式】

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

【样例输入】

1
xyz
3
xz
y
xzy

【样例输出】

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| \leq 10^3$

对于另外 20% 的数据，满足：$n\leq 100$

对于另外 20% 的数据，满足：$|s|, \sum |p_i| \leq 5 \times 10^4$

对于 100% 的数据，满足：$|s|, \sum |p_i| \leq 2 \times 10^5$

【来源】

HAOI 2017