洛谷 P3808 【模板】AC 自动机（简单版）

【模板】AC 自动机（简单版）

题目背景

警告：通过套取数据而直接“打表”过题者，是作弊行为，发现即棕名。

这是一道简单的 AC 自动机模板题，用于检测正确性以及算法常数。

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3
a
aa
aa
aaa
1
2
3
4
5

样例输出 #1

3
1

样例 #2

样例输入 #2

4
a
ab
ac
abc
abcd
1
2
3
4
5
6

样例输出 #2

3
1

样例 #3

样例输入 #3

2
a
aa
aa
1
2
3
4

样例输出 #3

2
1

提示

样例 1 解释

s 2 s_2 s