#P3735. [HAOI2017] 字符串

[HAOI2017] 字符串

题目描述

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

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

一、a=b |a| = |b|

二、对于所有 aibi a_i \neq b_i 以及 ajbj a_j \neq b_j ,满足 ij<k |i-j| < k

如果 a=bk |a| = |b| \le k ,那么认为 a=b a = b

输入格式

第一行一个整数 k k

第二行一个字符串 s s

第三行一个整数 n n ,接下来 n n 行每行一个字符串表示 pi p_i

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

输出格式

输出 n n 行,表示每个 pi p_i s s 中出现的次数。

1
xyz
3
xz
y
xzy
2
3
0

提示

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

对于 p2 p_2 y=x,y=y,y=z y = x, y = y, y = z ,同理。

对于 p3 p_3 xzyxyz xzy \neq xyz ,最大差 =1 = 1 不满足 <k=1 < k = 1

数据范围与提示

对于 20% 20\% 的数据,满足:s,Σpi103 |s|, \Sigma |p_i| \le 10^3

对于另外 20% 20\% 的数据,满足:n100 n \le 100

对于另外 20% 20\% 的数据,满足:s,Σpi5104 |s|, \Sigma |p_i| \le 5 \cdot 10^4

对于 100% 100\% 的数据,满足:s,Σpi2105 |s|, \Sigma |p_i| \le 2 \cdot 10^5