3368 - AC自动机(模板1)
时间限制 : 1 秒
内存限制 : 512 MB
给定 n 个模式串 si 和一个文本串 t,求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们编号不同。
输入
第一行是一个整数,表示模式串的个数 n。
第 2 到第 (n + 1) 行,每行一个字符串,第 (i + 1) 行的字符串表示编号为 i 的模 式串 si。
最后一行是一个字符串,表示文本串 t。
输出
输出一行一个整数表示答案。
样例
输入
3 a aa aa aaa
输出
3
输入
4 a ab ac abc abcd
输出
3
输入
2 a aa aa
输出
2
提示
样例 1解释
s2 与 s3 编号(下标)不同,因此各自对答案产生了一次贡献。
样例 2 解释
s1 ,s2 ,s4 都在串 abcd 里出现过。
数据规模
· 对于 50% 的数据,保证 n <= 1000。
· 对于 100% 的数据,保证 1 ≤ n ≤ 10^6, 1 ≤ ∣t∣ ≤ 10^6, 1 ≤ ∣si ∣ ≤
10^6 。
si , t 中仅包含小写字母。