Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

AC自动机学习笔记——浅谈AC自动机

写在更前面

这个一开始是dmf给我讲的
但是接下来反过来我还要给他讲?!
接下来是他的课件
这都不是重点
重点是第一页背景
AC自动机-佳木斯一中段明非

写在前面

这篇文章用来帮助像我一样不会指针的OIer们学习AC自动机
(下面是一段对话——出自某老师和某学生
“你会TRIE树么”“嗯”
“你会KMP么”“嗯”
“那你怎么不会AC自动机呢?!”

——————————————第一段扯淡结束————————————————————————
扯淡时间2——我来介绍AC自动机的历史吧
当然了最开始的时候我是以为能自动AC题呢(手动滑稽
Aho-Corasickautomation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法。
要学会AC自动机,我们必须知道字典树,也就是Trie树,又称单词查找树或键树,是一种树形结构,是哈希树的变种。
AC自动机一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有字典树Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。
——————————————一段算不上扯淡的扯淡结束——————————————————

既然提到了KMP和TRIE树

I.KMP
KMP处理的是字符串匹配问题
KMP中最重点的就是next数组了
毕竟不是重点说 我简单说
KMP的优点就在于
匹配字符串的时候我们不必按位寻找
毕竟不是每一位都能匹配的
我们用next数组来存储下次去哪里匹配
这就大大提升了效率
一道裸题:
题目描述
给你两个串A,B,可以得到从A的任意位开始的子串和B匹配的长度。
给定K个询问,对于每个询问给定一个x,求出匹配长度恰为x的位置有多少个。
N,M,K<=200000
输入说明:
第一行三个数 N,M,K,表示A的长度、B的长度和询问数。
第二行为串A。
第三行为串B。
接下来K行,每行1个数X。

输入
K行,对于每个询问每行输出一个数。

输出
K行,对于每个询问每行输出一个数。

样例输入
6 2 2
aabcde
ab
0
2
样例输出
4
1
代码

以上是KMP 不再过多进行赘述
II.TRIE树
这棵树可以但不限于把字符串踢上去
用来供我们寻找一些东西
利用公共前缀相同就合并的思想
大大减小复杂度
题目描述
现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含1个字母,至多75个字母。如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即前一个单词是后一个单词的前缀,则称词表为一个词链。例如下面单词组成了一个词链:
i
int
integer
但下面的单词不组成词链:
integer
intern
现在你要做的就是在一个给定的单词表中取出一些词,组成最长的词链,就是包含单词数最多的词链。将它的单词数统计出来,就得到密码了。

输入
第一行为单词表中的单词数N(1<=N<=2000),下面每一行有一个单词,按字典顺序排列,中间也没有重复的单词

输出
一行输出密码

样例输入
5
i
int
integer
intern
internet
样例输出
4
代码

这是TRIE树

正式表演来了

之前大概是预备知识 就没有过多进行赘述
下面是AC自动机了
到了AC自动机的时候我还是要关切的问一句
你们会预备知识了么
不会的话
你有几个任务需要执行
1.乖乖坐好

2.
3.
ok先假装你会了
上面第二段扯淡我说过 AC自动机是用来处理字符串匹配的
并且由两个预备知识组成
那么问题来了 AC自动机这么麻烦 好在哪里?
这样 我来一道题
给定一个字符串长度为m 和n个匹配串
当然你是支持用KMP的
但是
你的复杂度是O(n*m)——你需要对于每一个串在每个位置跑KMP
累不死你
所以面对这种棘手的问题 AC自动机站了出来
AC自动机的构造
1、构造一棵Trie树,作为AC自动机的搜索数据结构
2、构造fail指针,使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同KMP算法一样,AC自动机在匹配时如果当前字符匹配失败,那么利用fail指针进行跳转。由此可知如果跳转,跳转后的串的前缀,必定为跳转前的模式串的后缀并且跳转的新位置的深度(匹配字符个数)一定小于跳之前的节点。所以我们利用bfs在Trie上进行fail指针的求解。
3、扫描主串进行匹配。

上面是大体思路 接下来实现
(以下图是我自己画的 觉得不好看的话 忍着

里面一共有五个单词
she say him did dig
我已经按照字典树的规则把他们踢到了TRIE树上面
注意:
我们需要一个标记
这个标记用来告诉我们这个字母是否作为一个单词的结尾
后面会用到
这里不进行过多的赘述
接下来是AC自动机的精华——fail指针
先说说Fail指针是个啥
失败了?WA了?
当然不是
Fail取字面意思就是说我们在当前位置匹配失败
那么在匹配出现问题之后
我们就需要重新进行匹配
和刚刚提到的KMP原理类似 我们需要找到一个方法快速跳转
我也不知道为什么在两个地方这种功能的同一个东西会有不一样的名字
总之 fail指针让我们快速跳转
这也是AC自动机算法很优的原因所在
那么 就用我刚才那棵非常丑的TRIE树来匹配一下下
STEP1.根节点没有fail指针 我们可以把它处理成一个不可能的数或者不管他
STEP2.把根节点的直接子节点的fail指针给到根节点(下图

这一步的正确性是显然的 毕竟你要是连一个字符都匹配不上的话只能重新开始
STEP3.下一步采用类似于BFS的思想
我们人为把这棵树分成很多层
每次BFS的是一层
把这个推进去之后
我们用他的父亲节点的fail作为匹配的找寻
搜索终止条件有两个
大家可以yy一下就是说这个点匹配不成功了
用KMP的思想 我们去寻找下一个能匹配的
换句话说 在这个节点的父节点的fail的子节点中如果出现了相同字母
那么我们的fail就给到它
第二种情况就是没有 找不到
这个时候fail指向根节点
就这样一直就匹配fail了
下面是我那棵树fail匹配过程
第二层的匹配

红笔是这一步的匹配
我来简单讲解一下
第二层左侧的H点 它的父节点的fail是根 根的直接儿子中有H 满足搜索终止条件
fail给到H
下一个A同理 根的直接子节点中没有A 所以这个时候fail指到根节点
接下来不进行过多的赘述 相信大家已经懂了
这个位置确实非常绕 多理解理解 我是听了三遍讲课加上一次自学才弄懂一点的
PS:所有过程的代码实现都在最下方,我会标注注释供大家理解
当我说的最重要的步骤结束了之后 AC自动机已经构建完毕了
我们需要的匹配串听令 排好队 接受匹配(雾
在这个过程中 我们会遇到 并且只能遇到两种情况
第一种:
我们在当前的树节点进行匹配 发现我们匹配到了结尾
这个时候我们的匹配成功了一次
不管当前的位置是不是这个树链(就这么形容吧)的结尾
我们匹配成功了 这个时候我们的单词数目+1
然后进行如下操作:
通过这个最后字母的节点跳fail
每跳到一个进行询问
如果有标记证明这是一个单词的结尾
恭喜你又找到了一个单词
这个时候再+1
第二种:
匹配不下去了
根据刚才的经验
我们需要跳fail
我们知道fail指针之前的文本是不用我们担心的 一定匹配
这个时候重新向下匹配
有点像一个循环
终止条件有两个:
1.我们匹配成功
这个时候执行第一种的后续操作 查找结束
2.没有了
我们全都找过了
可就是没有
这个时候我们只好宣布放弃

举两个例子
以我刚才的树举例
第一个 我要找的是SHIM(虽然这不是单词
从左侧S->H发现再往下不对了
跳H的fail继续匹配 这个时候来到了中间那列的H
发现下面正好匹配结束
然后执行后续操作
跳M的fail发现跳到根了 本次搜索结束
第二个 我要找的是dit(也不是个单词
从右侧D->I发现下面不对了
跳I的fail回到了根
这个时候证明我们找不到这个单词
其实还是比较简单的
就是代码可能相对来讲用数组实现要复杂

例题选讲

以下内容是2018.2.24更新
用一道题讲解一下
传送门
这道题是纯的裸题 裸的不行
讲解已经完毕 接下来给出代码 里面有详细的注释

接下来给出一道例题(并不裸
传送门
这个题需要的是思考,灵活运用fail指针
题解

以下内容为了dsfz多校联训准备
由于这个讲课计划来的太突然了
所以我只能暂时给出一句话题解
之后详细的题解会尽快发布到博客上面
大家可以追踪一下(相信大家都不需要
更多例题:
1.[HNOI2004]L语言
传送门
设F[i]表示长度为i的前缀是否可表示
由于单词长度<=10,所以我们可以暴力转移
即F[i]=(F[i-1]&&can(i,i))||(F[i-2]&&can(i-1,i))||…||(F[i-10]&&can(i-9,i))
其中can(i,j)表示i到j这段子串是否是一个单词
这一步我们可以在AC自动机上O(j-i+1)跑一遍来得到

这样总时间复杂度上限为O(文章总长度*100)

但是:接下来出问题了
我能不能不用AC自动机做这题
答案是能的
这个我写了题解
传送门

2.Poi病毒
这个题相信大家都做过
所以不给题目链接了 听我口胡吧

3.[JSOI2007]文本生成器
传送门
满足条件的字符串总数=26^M-不包含这N个字符串的串的数量
设F[i][j]表示匹配前i个字母之后走到了AC自动机的j号节点的方案数
则有对于任意的j的儿子节点x
若x不是危险节点,则F[i+1][x]+=F[i][j]
最后把所有不是危险节点的F[M][x]求和即是不包含这N个字符串的串的数量
用26^M减去即可

更多请见另外一篇文章中给出的ppt里面有更多的例题
不过多进行赘述

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏