#544. AC 自动机(加强版)

AC 自动机(加强版)

题目描述

给你一个文本串 SSnn 个模式串 T1nT_{1 \sim n},请你分别求出每个模式串 TiT_iSS 中出现的次数。

输入格式

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

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

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

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

输出格式

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

5
a
bb
aa
abaa
abaaa
abaaabaa
6
0
3
2
1

1n2×1051 \le n \le 2 \times {10}^5

T1nT_{1 \sim n} 的长度总和不超过 2×1052 \times {10}^5

SS 的长度不超过 2×1062 \times {10}^6