#F. 洛谷P5357 AC自动机（二次加强版）

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

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

第一行包含一个正整数$n$表示模式串的个数。

接下来$n$行，第$i$行包含一个由英文字母构成的字符串$T_i$。

最后一行包含一个由英文字母构成的字符串$S$。

对于$T_i$ ，我们限制$T_i$的值只为$“Diana"$，$“DianaDiana"$，$“DianaDianaDiana"$其中一个

**数据不保证任意两个模式串不相同**。

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

4
Diana
DianaDiana
DianaDianaDiana
Diana
DiananaDiana

$1≤n≤2×10^5$，$T_{1..n}$ 的长度总和不超过 $2×10^5$，$S$ 的长度不超过 $8×10^5$