要学AC自动机需要自备两个前置技能:KMP和trie树(其实个人感觉不会kmp也行,失配指针的概念并不难)
其中,KMP是用于一对一的字符串匹配,而trie虽然能用于多模式匹配,但是每次匹配失败都需要进行回溯,如果模式串很长的话会很浪费时间,所以AC自动机应运而生,如同Manacher一样,AC自动机利用某些操作阻止了模式串匹配阶段的回溯,将时间复杂度优化到了 O ( n ) O(n) O(n)(n)为文本串长度
ac自动机,就是在tire树的基础上,增加一个fail指针,如果当前点匹配失败,则将指针转移到fail指针指向的地方,这样就不用回溯,而可以路匹配下去了.(当前模式串后缀和fail指针指向的模式串部分前缀相同,如abce和bcd,我们找到c发现下一个要找的不是e,就跳到bcd中的c处,看看此处的下一个字符(d)是不是应该找的那一个)
一般,fail指针的构建都是用bfs实现的,每个模式串的首字母肯定是指向根节点。。。。
课程介绍
课程目录
往期学员作品
用户评论
课程介绍
课程目录
往期学员作品
用户评论
你将获得
- 深刻理解AC自动机的算法
教学服务
录播课程
讲师介绍
课程详情
温馨提示
- 请勿私下交易请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
- 听课说明
1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课
2、手机/平板:下载腾讯课堂APP, 进入学习页面听课