【模板】AC自动机(二次加强版)

题目描述

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1..n}$,请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

输入输出格式

输入格式


第一行包含一个正整数 $n$ 表示模式串的个数。 接下来 $n$ 行,第 $i$ 行包含一个由小写英文字母构成的字符串 $T_i$。 最后一行包含一个由小写英文字母构成的字符串 $S$。

输出格式


输出包含 $n$ 行,其中第 $i$ 行包含一个非负整数表示 $T_i$ 在 $S$ 中出现的次数。

输入输出样例

输入样例 #1

5
a
bb
aa
abaa
abaaa
abaaabaa

输出样例 #1

6
0
3
2
1

说明

$1\le n\le 2\times10^5$,$T_{1..n}$ 的长度总和不超过 $2\times 10^5$,$S$ 的长度不超过 $2\times10^6$。