3792 - 【模板】AC 自动机(简单版)
描述

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

输入

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

输出

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

样例

输入

3
a
aa
aa
aaa

输出

3

输入

4
a
ab
ac
abc
abcd

输出

3

输入

2
a
aa
aa

输出

2
提示
样例 1 解释

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

样例 2 解释

s_1,s_2,s_4 都在串 abcd 里出现过。

数据规模与约定
  • 对于 10\% 的数据,保证 n = 1。
  • 对于 100\% 的数据,保证 1 \leq n \leq 10^6,1 \leq |t| \leq 10^6,1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6。s_i, t 中仅包含小写字母。
来源
洛谷 P3808 【模板】AC 自动机(简单版)
标签
题目参数
时间限制 2 秒
内存限制 256 MB
提交次数 1
通过次数 1