重新学 /(AC/) 自动机发现以前就像没见过一样……
首先是一段经典的话：“/(AC/) 自动机是 /(trie/) 树上跑 /(kmp/)”
于是 /(AC/) 自动机的关键在于运用 /(nxt/) 进行匹配
由于这时的 /(nxt/) 形成一棵树形结构，可以将一些匹配问题转化为树上问题
如果 /(x/) 匹配到了文本串，那么所有 /(x/) 的祖先也都是可以匹配上的
那么经常可以通过统计祖先的前缀和来方便地维护
动态题目可以用树状数组等结构来维护子树信息
另外，为了加快失配匹配，可以建立虚儿子，于是匹配可以连续进行
至于具体的图就先不模拟了
一定注意一个大坑点是在这种 /(trie/) 图上父亲的特殊标记是要下传到儿子上的
注意父亲的编号不一定比儿子的小，因此这部分递推要写在 /(bfs/) 里，不能直接 /(for/) 循环！！！
另外补充一点，可以发现 /(AC/) 自动机的构建过程复杂度是要乘上字符集大小的，如果字符集较大，我们可以用主席树来构建，因为写出转移会发现大部分儿子都是从 /(nxt_i/) 继承过来的
/(AC/) 自动机上的 /(dp/)
/(AC/) 自动机上的 /(dp/) 一般都设 /(f[i][j]/) 表示长度为 /(i/) 的串结束于 /(j/) 节点的情况，那么转移相当于枚举所有的儿子进行移动
还有就是 /(dp/) 的过程中尽量通过改变自动机的样子来调整 /(dp/)，而不是无脑往上加状态
比如要求到达关键串停止，其实没有必要增加状态记录有没有到达关键串，而是直接把自动机上所有关键串的儿子指向自己即可
设 /(f[i][j][0/1]/) 表示长度为 /(i/) 且结束于 /(j/) 节点，卡不卡上限的方案数
那么模拟题意进行转移即可
对于前导零的情况可以初始化时给 /(f[len][trie[0][j]][0]/) 进行赋值
不合法的串建立 /(trie/) 树时顺便打标记，注意需要把 /(nxt[x]/) 的标记继承过来
这个分类讨论就过于阴间了……
直接考虑 /(L=2/) 的情况，发现从 /(f[i]/) 转移到 /(f[i+1]/) 或 /(f[i+2]/)
而在 /(AC/) 自动机上的转移方程都是固定的
那么可以把这两行放进矩阵里进行转移
这道题 也是一样的道理，居然还是个黑题
结合树上问题
首先插入操作都直接用于构建 /(AC/) 自动机即可
对于询问 /((x,y)/) 的本质相当于求 /(fail/) 树上 /(x/) 的子树内有多少节点是 /(y/) 串内的
考虑 /(y/) 串在 /(trie/) 上走过的路径即是整个串中的节点
那么可以把询问离线，然后遍历整棵 /(trie/) 树，而在 /(fail/) 树上的子树关系通过树状数组维护 /(fail/) 树中的 /(dfs/) 序来得到
注意遍历 /(trie/) 树的时候不能直接用原来的 /(trie/) 数组，因为已经经过 /(AC/) 自动机的改造变成了一张图，需要备份
一样的道理，每次在 /(fail/) 树上进行单点加和子树和的操作即可
还是一样的套路，只不过变成了改变一个串的权值
一个串的权值在 /(fail/) 树上影响的范围仍然是一个区间，那么直接在线段树上开 /(multiset/) 来维护这个区间的权值集合，查询时拿出最大值，修改时先删后加入
非常神奇的一个题
首先明确枚举的是母串 /(t/)，然后寻找有多少符合条件的子串 /(s/)
对于一个 /(s/) 需要满足的条件其实是有两部分组成：能够作为满足条件 /(3/) 的子串；每次出现时都是满足条件 /(3/) 的
换句话说其在 /(t/) 中出现的次数是等于满足条件 /(3/) 出现的个数
第一个是自动机上用树状数组维护的基本操作，来看第二个怎么求
可以倒序枚举 /(t/) 的每一位，找到一个能匹配后缀的最靠前的串，并且不存在一个之前匹配的串的将其包含
其中最靠左的一个串可以预处理的时候顺便求出
以前写得有点儿抽象，重新来写一发
首先所有备选的串 /(s/) 一定是 /(fail/) 树上 /(t/) 代表的每一个节点上的其它字符串（这个结束位置要事先在 /(trie/) 图上往下转移一下）
考虑怎样选出这些字符串中满足第三个条件的那些
首先这些串之间不能有包含关系，也就是说如果在串上显式地被包含，就不能加入候选集合了
这个可以从前往后扫的时候维护出当前最靠后的位置，只把在这个位置之前的串加入
于是目前得到了一些互不相交的候选串
但是在这样的情况下仍然有可能被包含，那么我们就用上面提到的出现次数相等来判断
即这个串目前在候选集合中出现的次数=其在 /(t/) 串中出现的总次数即可
非常规题
发现一个串能够延续本质相当于在 /(AC/) 自动机上有一个没被打过标记的儿子可以走过去，而无限延伸需要自动机上有一个没被标记的环即可
CF1202E You Are Given Some Strings…
第一步就没有想到……
发现题目要求的是拼接 /(s/) 去匹配 /(t/)，那么可以拆分 /(t/) 来匹配 /(s/)
枚举 /(t/) 上的一个断点，断点前的一个后缀匹配一个 /(s/)，断点后的一个前缀匹配一个 /(s/)，那么两部分都转化为 /(AC/) 自动机可以维护的经典问题
一个没见过的重构套路——二进制分组
每次加入一个字符串时都新建一棵大小为 /(1/) 的 /(AC/) 自动机
然后用类似于 /(2048/) 一样的方式开始合并相同大小的自动机，那么最后留下的一定最多只有 /(log/) 个，而每个字符串最多经过 /(log/) 次重构
再来考虑删除的问题，发现维护的信息是具有可减性的，那么对于需要删除的串也建立一遍 /(AC/) 自动机然后减一减即可
但是实现起来会非常麻烦，最主要来源于平常的 /(AC/) 自动机默认根是零，而数组恰好也是零，而这里根不再是零时，数组相应地也要进行初始化的改变
遇到一个玄学问题，将 /(char/) 复制到 /(string/) 时会 /(RE/)，而如果采用初始化为空格之后采用 /(+/) 的方式来插入则不会有问题
/(update/)：现在来看一点儿也不玄学了好吧
Summary
- /(AC/) 自动机能干得事无非就是多模匹配，直接往这方面想即可
- 套路主要就是 /(dp/) 和树上问题，/(dp/) 经常容易漏掉
原创文章，作者：wdmbts，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/277191.html