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

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

Input

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

Output

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

Examples

Input

3
a
aa
aa
aaa

Output

3

Input

4
a
ab
ac
abc
abcd

Output

3

Input

2
a
aa
aa

Output

2
Hint
样例 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 中仅包含小写字母。
Source
洛谷 P3808 【模板】AC 自动机(简单版)
Tags
题目参数
Time Limit 2 seconds
Memory Limit 256 MB
提交次数 1
通过次数 1