#PQJ2600x15500. QOJ 2600_15500

    ID: 2844 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HAOI 2017字符串双指针

QOJ 2600_15500

给出一个字符串 𝑠 和 𝑛 个字符串 𝑝 𝑖 ,求每个字符串 𝑝 𝑖 在 𝑠 中出现的次数。注意这里两个字符串相等的定义稍作改变。

给定一个常数 𝑘 ,对于两个字符串 𝑎 , 𝑏 ,如果 𝑎

𝑏 ,那么满足:

| 𝑎 |

| 𝑏 | ; 对于所有 𝑎 𝑖 ≠ 𝑏 𝑖 以及 𝑎 𝑗 ≠ 𝑏 𝑗 ,满足 | 𝑖 − 𝑗 | < 𝑘 。

如果 | 𝑎 |

| 𝑏 | ≤ 𝑘 ,那么认为 𝑎

𝑏 。

输入格式

第一行一个整数 𝑘 。

第二行一个字符串 𝑠 。

第三行一个整数 𝑛 ,接下来 𝑛 行每行一个字符串表示 𝑝 𝑖 。

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

输出格式

输出 𝑛 行,表示每个 𝑝 𝑖 在 𝑠 中出现的次数。

样例数据 样例 1 输入 1 xyz 3 xz y xzy 样例 1 输出 2 3 0 样例 1 解释

对于 𝑝 1 , 𝑥 𝑧

𝑥 𝑦 , 𝑥 𝑧

𝑦 𝑧 ,因为都只有一个位置差异。

对于 𝑝 2 , 𝑦

𝑥 , 𝑦

𝑦 , 𝑦

𝑧 ,同理。

对于 𝑝 3 , 𝑥 𝑧 𝑦 ≠ 𝑥 𝑦 𝑧 ,最大差

1 不满足 < 𝑘

1 。

子任务

对于 20 % 的数据, | 𝑠 | , ∑ | 𝑝 𝑖 | ≤ 10 3 ;

对于另外 20 % 的数据, 𝑛 ≤ 100 ;

对于另外 20 % 的数据, | 𝑠 | , ∑ | 𝑝 𝑖 | ≤ 5 ⋅ 10 4 ;

对于 100 % 的数据, | 𝑠 | , ∑ | 𝑝 𝑖 | ≤ 2 ⋅ 10 5 。