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

  • 2018-10-10
  • 11
  • 0

Description:

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

Input:

第一行一个n,表示模式串个数;

下面n行每行一个模式串;

下面一行一个文本串。

Output

一个数表示答案

Sample Input:

2
a
aa
aa

Sample Output:

2

题目链接

顾“题”思义,题目是一个AC自动机的模板裸题。

AC自动机就是将多个模式串建立字典树(Trie Tree),在树上进行类KMP操作,以此与主串进行匹配。

AC自动机详解:

AC自动机

AC代码:

评论

还没有任何评论,你来说两句吧