#2278. 「HAOI2017」字符串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: __stdcall

题目描述

给出一个字符串 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

样例解释

对于 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