#M092. [模板]ac自动机之三

    ID: 6070 传统题 1000ms 256MiB 尝试: 16 已通过: 8 难度: 6 上传者: 标签>CF1900提高AC 自动机fail 树统计难度分类

[模板]ac自动机之三

题目背景

本题原为“AC 自动机(二次加强版)”。完成本题前可以先完成 [模板题]ac自动机之一和 [模板]AC 自动机之二两道题,为 AC 自动机更简单的应用。

题目描述

给你一个文本串 SS 和 nn 个模式串 T1∼nT_{1 \sim n},请你分别求出每个模式串 TiT_i 在 SS 中出现的次数。

输入格式

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

接下来 nn 行,第 ii 行包含一个由小写英文字母构成的非空字符串 TiT_i。

最后一行包含一个由小写英文字母构成的非空字符串 SS。

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

输出格式

输出包含 nn 行,其中第 ii 行包含一个非负整数表示 TiT_i 在 SS 中出现的次数。

样例 #1

样例输入 #1

5
a
bb
aa
abaa
abaaa
abaaabaa

样例输出 #1

6
0
3
2
1

提示

对于 100%100 \% 的数据,1≤n≤2×1051 \le n \le 2 \times {10}^5,T1∼nT_{1 \sim n} 的长度总和不超过 2×1052 \times {10}^5,SS 的长度不超过 2×1062 \times {10}^6。