4300: 「HAOI2017」字符串
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给出一个字符串 $ 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
xyz
3
xz
y
xzy样例输出 复制
2
3
0提示
数据范围：对于 $ 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 $。