#O1109. 多模式串匹配

多模式串匹配

题目描述

给定一个文本串 TT 和 nn 个模式串 P1,…,PnP_1,\dots,P_n,对每个模式串,求它在文本串中出现的次数(出现可以重叠)。

输入格式

第一行一个字符串 TT。

第二行一个整数 nn。

接下来 nn 行,每行一个字符串 PiP_i。

输出格式

共 nn 行,第 ii 行一个整数,表示 PiP_i 在 TT 中的出现次数。

样例 #1

样例输入 #1

aaaaa
3
a
aa
aaa

样例输出 #1

5
4
3

数据规模与约定

数据范围 说明
$1 \le T
1≤n≤1041 \le n \le 10^4 模式串个数
$1 \le \sum P_i
字符集 均为小写英文字母
  • 重叠出现也要计数,例如 aa 在 aaa 中出现 2 次。
  • 不同模式串可能相同,此时各自输出相同的答案。