A6817. 「HAOI2017」字符串
编程题
NOI/NOI+/CTSC
知识点
题目描述
给出一个字符串 $s$ 和 $n$ 个字符串 $p_i$，求每个字符串 $p_i$ 在 $s$ 中出现的次数。注意这里两个字符串相等的定义稍作改变。
给定一个常数 $k$，对于两个字符串 $a,b$，如果 $a=b$，那么满足：
$|a|=|b|$；
对于所有 $a_i\ne b_i$ 以及 $a_j\ne b_j$，满足 $|i-j|<k$。
如果 $|a|=|b|\le k$，那么认为 $a=b$。
给定一个常数 $k$，对于两个字符串 $a,b$，如果 $a=b$，那么满足：
$|a|=|b|$；
对于所有 $a_i\ne b_i$ 以及 $a_j\ne b_j$，满足 $|i-j|<k$。
如果 $|a|=|b|\le k$，那么认为 $a=b$。
输入格式
第一行一个整数 $k$。
第二行一个字符串 $s$。
第三行一个整数 $n$，接下来 $n$ 行每行一个字符串表示 $p_i$。
所有的字符 ASCII 码在 $33$ 至 $126$ 之间。
第二行一个字符串 $s$。
第三行一个整数 $n$，接下来 $n$ 行每行一个字符串表示 $p_i$。
所有的字符 ASCII 码在 $33$ 至 $126$ 之间。
输出格式
输出 $n$ 行，表示每个 $p_i$ 在 $s$ 中出现的次数。
输入输出样例
输入 #1
1 xyz 3 xz y xzy
输出 #1
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 $。
对于另外 $ 20\% $ 的数据，$ n \le 100 $；
对于另外 $ 20\% $ 的数据，$ |s|, \sum |p_i| \le 5 \cdot 10^4 $；
对于 $ 100\% $ 的数据，$ |s|, \sum |p_i| \le 2 \cdot 10^5 $。