洛谷P3808自动机（简单版）

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

题目背景

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

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

题目描述

设有n个字符串集合s_i和一个主字符串t" ，求有多少个不同编号的字符串存在于该主字符串中？"若且唯其两者的索引号不同，则认为这两个字符串不同。"

输入格式

第一行为一个整数n。
从第二行至(n+1)行共计n行数据输入结束标志，请注意以下几点：
每一条数据输入的第一列为对应编号i；
其余部分则对应编号为is_i$；
最后一行为一个字符串t即待匹配文本。

输出格式

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

样例 #1

样例输入 #1

    3
    a
    aa
    aa
    aaa

样例输出 #1

    3

样例 #2

样例输入 #2

    4
    a
    ab
    ac
    abc
    abcd

样例输出 #2

    3

样例 #3

样例输入 #3

    2
    a
    aa