uniHk

AC自动机

01Trie(5) CDQ分治(4) dsu on tree(1) K-D Tree(5) 主席树(5) 各类说明(1) 后缀数组(1) 后缀自动机(11) 回文自动机(6) 字符串（杂）(6) 康托展开(1) 数学(7) 整体二分(1) 斜率优化DP(3) 树链剖分(3) 概率DP(2) 算法(Lazy)(38) 线性基(5) 莫队(6) 计算几何(3)

/ 注册

全部文章 / AC自动机（共7篇）

AC自动机(Automaton)

小小总结千万记住insert完以后要build!!!老是忘掉QAQ insert函数就只是trie数的插入函数，可在结尾根据条件打一些标记 build函数(构建fail树)，主要利用BFS match函数中跑fail树其实就是反复跑后缀 fail树上倒过来建树以后可以进行很...

2020-01-02

0 431

洛谷-P4052+P3311 （AC自动机+数位DP）

洛谷-P4052 文本生成器题目地址虽然这题应该称为记忆化搜索，但是就想当做数位DP(QAQ) 一开始数组开小了，导致了WA，TLE，RE以及两个AC，深深的体会到了数组开小了什么错误都有，哈哈题意：给出一个字典，求长度为M且包含字典中至少一个单词的文本有多少个。思路：虽...

2020-01-02

0 701

洛谷 P-2292 L语言(AC自动机)

洛谷 P-2292 L语言一道比较简单的题，结果自己脑补了各种奇葩(错误)的判断，搞了一个多小时。。。题意：用已知字典去识别一个串，求最长可识别前缀（指能将此前缀分解为字典里面的单词）思路：建好AC自动机，记录好每个点所代表的字符串的长度拿要匹配的串从前往后匹配，若某个点...

2020-01-02

0 404

洛谷 P3041 视频游戏的连击Video Game Combos(AC自动机+拓扑排序+数位DP)

洛谷 P3041 视频游戏的连击Video Game Combos 难度一般，不过这个数位DP其实应该叫做记忆化搜索题意：玩游戏时可以通过按键组合打出combo技能；然后是已知N个combo的按键方式，然后求K次按键最多可以放出的combo技能（combo技能之间可以重叠）。思路： ...

2020-01-02

0 497

洛谷 P-4045 密码(AC自动机+状态压缩+数位DP+乱搞)

洛谷 P-4045 密码记AC的第一道黑题！题意：已知一段密码包含了一些字符串，然后求满足条件的密码有多少个，数量小于42时还得全部输出思路：一开始WA了两个点，不知道WA的什么，索性把读入的字符串去重了，实际上不需要建好AC自动机，同时记录当前点是哪个字符串的结尾，方便...

2020-01-02

0 566

最短母串问题（AC自动机+BFS+状态压缩）

最短母串问题题意：给定 n n n个子串，求最短且字典序最小的母串（母串性质：这 ...

2020-01-02

0 639

Censoring (Gold)（AC自动机多字符串匹配+栈）

Censoring (Gold) 题意：给了一段文本串，再给了含 N N N个字符串的字典。将文本从左到右，如果遇到了字典中的字符串，则删...

2020-01-02

0 497