AC自动机（模板1）

题目描述

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

输入

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

输出

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

样例

提示

样例 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 中仅包含小写字母。