#PQJ2600x15500. QOJ 2600_15500
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 。