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

题目背景

# 通过套取数据而直接“打表”过题者,是作弊行为,发现即棕名。 这是一道简单的AC自动机模板题。 用于检测正确性以及算法常数。 为了防止卡OJ,在保证正确的基础上只有两组数据,请不要恶意提交。 **管理员提示:本题数据内有重复的单词,且重复单词应该计算多次,请各位注意**

题目描述

给定n个模式串和1个文本串,求有多少个模式串在文本串里出现过。

输入输出格式

输入格式


第一行一个n,表示模式串个数; 下面n行每行一个模式串; 下面一行一个文本串。

输出格式


一个数表示答案

输入输出样例

输入样例 #1

2
a
aa
aa

输出样例 #1

2

说明

subtask1[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6,n=1; subtask2[50pts]:∑length(模式串)<=10^6,length(文本串)<=10^6;