AC 自动机（简单版）

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

给定 $n$ 个带编号的模式串 $s_1,s_2,\ldots,s_n$ 和一个文本串 $t$，求有多少个模式串在文本串中至少出现一次。

两个内容相同但编号不同的模式串仍视为两个不同模式串；如果它们都在文本中出现，应分别计数。所有字符串均只包含小写英文字母。

输入格式

第一行输入模式串数量 $n$。

接下来 $n$ 行，第 $i$ 行输入模式串 $s_i$。

最后一行输入文本串 $t$。

输出格式

输出一个整数，表示在文本串中出现过的模式串编号数。

样例输入 1

3
a
aa
aa
aaa

样例输出 1

3

样例输入 2

4
a
ab
ac
abc
abcd

样例输出 2

3

样例输入 3

2
a
aa
aa

样例输出 3

2

数据范围

对于所有数据，$1\le n\le10^6$，$1\le |t|\le10^6$，$1\le\sum_{i=1}^{n}|s_i|\le10^6$。