#540. AC 自动机(简化版)

AC 自动机(简化版)

题目背景

这是一道简单的 AC 自动机模板题,用于检测正确性以及算法常数。

题目描述

给定 nn 个模式串 sis_i 和一个文本串 tt,求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。

输入格式

第一行是一个整数,表示模式串的个数 nn。 第 22 到第 (n+1)(n + 1) 行,每行一个字符串,第 (i+1)(i + 1) 行的字符串表示编号为 ii 的模式串 sis_i。 最后一行是一个字符串,表示文本串 tt

输出格式

输出一行一个整数表示答案。

3
a
aa
aa
aaa
3
4
a
ab
ac
abc
abcd
3
2
a
aa
aa
2

样例解释

样例 1 解释

s2s_2s3s_3 编号(下标)不同,因此各自对答案产生了一次贡献。

样例 2 解释

s1s_1s2s_2s4s_4 都在串 abcd 里出现过。

数据范围

1n1061 \leq n \leq 10^6

1t1061 \leq |t| \leq 10^6

1i=1nsi1061 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6

si,ts_i, t 中仅包含小写字母。