#M090. [模板题]ac自动机之一

    ID: 4667 传统题 1000ms 256MiB 尝试: 35 已通过: 17 难度: 5 上传者: 标签>CF1700普及+/提高-AC 自动机fail 树统计广度优先搜索难度分类

[模板题]ac自动机之一

Description

给你N个单词,然后给定一个字符串,问一共有多少单词在这个字符串中出现过(输入相同的字符串算不同的单词,同一个单词重复出现只计一次)。

Format

Input

第一行一个整数N,表示给定单词的个数。

接下来N行,每行输入一个长度不超过50且全由小写字母组成的单词。

最后一行输入一个长度不超过1000000的字符串。

N≤10000

Output

输出一行包含一个整数,表示共在给定字符串中出现过的单词个数。

Samples

5
she
he
say
shr
her
yasherhs
3