当前位置:首页 > 字符串 > AC自动机 > 正文
洛谷P3796【模板】AC自动机(简单版)
2407+

题目大意:给定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;

解题思路

AC自动机模板题,即Trie树+KMP模式匹配。

首先,将所有模式串建立到一棵Trie树,然后对文章的逐个字母进行查找。

查找主要考虑匹配失败怎么处理。跟KMP算法一样,求出最长公共前后缀,就知道失配后跳到哪个位置了。

预处理p数组(next数组),p[i]表示根结点到结点p[i]这段前缀和同等长度的以结点i结尾的后缀匹配成功(根结点无字符,默认根结点1到根结点1匹配成功):

如果i的下一个结点匹配失败(代码28行),那么保留原来匹配过的,即p[i]之前都不需要再匹配,由于匹配失败即不存在该结点,我们可以直接修改其指针至p[i]的对应儿子,这样就可以继续、一直、“递归”找下去了;

如果i的下一个结点匹配成功(代码33行),那么i的下一个结点与p[i]的对应儿子相同就指向该儿子,不相同就“往回退”,往回退这一步在之前失配时指针已经链接好了。

需要注意的是,首字母没有公共前后缀的时候,p[i]是0,而根结点编号是1,根结点到根结点匹配成功应该链到1,故让结点0的儿子全为1。(若根结点从0编号,那么单个字符也有公共前缀了)

程序实现

代码解释:

22行之前:建立Trie树;

23行:0结点所有儿子指向1

24-36行:广搜计算next数组,失配时结点为空,广搜过程中,将next数组存入了空结点了

38-44行:匹配字符串,a的结点编号,顺着儿子往下找,找到累加单词数,找不到指针会自动往回退。

About

坚决不Copy代码!

本文标签:,,,,,,,,

洛谷P3796【模板】AC自动机(简单版):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!