AC自动机好题，恐怕出题人都完全没有想到是AC自动机。
队友在写这题的时候突然发现了AC自动机的题解。
我看了一下发现还真是板子题。
正文：
WTM！！！！想打人！！！！！！！！！
Shit！！！
淦，再也不为了缩行偷懒了
这题我真的写了好久，今天刚刚发现错误，真的真的真的就是一个板子题，不过要转换一下并且check一下长度就可以了。
但是！！我为了偷懒，在输出的时候，就把答案清零了，这就导致了相同前后缀的答案错误！！！
题意：
给你很多字符串。再给你多组前后缀，问这几组前后缀在以上字符串的出现次数。
思路：
将前缀prefix 与 后缀 suffix 通过一个非字母字符连接，插入到trie中。
再将模式串通过相同的非字母字符连接，对其跑一边AC 自动机记录一下答案就可以了。
需要注意的地方就是模式串的长度不能小于后缀+前缀。
AC Code
#include
后缀数组求最长不重叠重复子串的入门题。 论文题。 也是男人八题之一。 想我活了十多年终于成了 ( \dfrac {2} {8}) 个男人 虽然说是入门题，但也没有那么简单。 说到底，这道题是我第一次将后缀数组应用起来。我意外的发现，后缀数组之所以强大，在于它拆分了所有后缀，然后又构造了 height 数组描述前缀。这就掌握了所有连续子串。 神了！ 这里还是说一下我对最长不重叠重复子串求法的理解。 直接求最长不重叠重复子串是困难的，但对于一个确定的长度 len ，我们却可以( O\left( n \right) ) 地判断其可行性。而这长度又具有单调性，这就使得我们可以用二分的思维去解决它。可行性判断方法如下： 前面说了，sa + height 可以用来描述子串 不是所有。不考虑其它，height 可以单纯的描述为存在的一个公共子串长度。而这个长度大于 len 是我们的必要条件。接下来要判断的就是是否会产生重叠。 sa数组记录的是这个公共子串所对应的后缀起始位置，如果两个后缀它们的起始位置大于等于 len ,毫无疑问，不会重叠。…
好题。但kuangbin说这道题已经是很简单的DP了。 首先kuangbin并没有说错，但是该题的解题思维有点难想到。 如果你按照题意去解题，那你是想不出来的。 还是重在转化啊………… 题意： 给你很多串DNA病毒序列，再给你一串待修复的DNA序列。现在待修复的DNA序列中可能包含病毒序列。 我们的工作是要求修改最少的次数使得待修改序列中不含病毒序列。 问最少次数。 思路： 不要想着去寻找如何修改，有个简单的思路是去寻找所有不含病毒序列的DNA序列，并求出与原串不同的字符数量。然后找出最小值。 但这显然复杂度是很高的。我们可以考虑用DP求解。 记( dp \left[ len \right] \left[ status \right] ) 为当前长度为len，状态结点为 status 时需要修改的最少次数。 那么对下一状态，我对于下面四个结点，如果所组成的字符串构成了病毒串，那么不成立，否则如果当前字符与原字符串当前位置相同，则不需要花费。否则，需要改变一次，花费 + 1。 转移方程 $ dp\left[ len + 1 \right] \left[…
AC自动机+状压DP的入门题 虽然不是很好意思，但我的确是先看了kuangbin的代码再敲的。 从AC自动机构建矩阵开始起的出现的那个结点状态，在之后做题中越來越显著。 因为AC自动机本身也没多少地方可以改了，这是一个成熟的算法。而考研我们的运用就只能在理解熟悉它的状态，并运用它的状态。 关于状态应用最明显的就是DP了。 这题之后尽量不看题解…… 说了一堆废话，下面放题解。 题意： 有一个长度为 n 的密码，给你一个 m 个字符串的集合。告诉你这个密码必定会包含这集合中的 k 个。 问密码的种数。 思路： 这道题应该是给出一个状态就很好理解了。 开一个三维数组，记 ( dp\left[ i \right] \left[ j \right] \left[ k \right] ) 为长度为 ( i ) ，在第( j ) 个结点，含有字符串数量的状态为 ( k ) 的可构字符串数量。 每次在AC自动机上跑的时候更新一下状态，最后再将包含字符串数量大于等于 k…
昨天晚上从Yasola那里偷来的一道题…… 为什么Yasola这么优秀啊！！！！！ 求求你别学了，我已经完全跟不上了…… 因为看着题目并不是很难我也就写了一蛤，然后自以为是无脑题就疯狂WA…… emmmm…… 其实仔细想想还是挺简单的。 题意： 给你一张无向图，要你找出最小环。 点数 ( n \leq 100 ) 思路： 对 floyd 进行简单增加一点代码。 floyd 算法剖解开来就是不断找到一个中间结点使得路径更短。而我们可以在这个中间结点加入最短路之前，将其固定为环上的一个点，这点必定不会被所有最短路夹在中间。 有一个非常显然的问题就是，当我固定一个中间结点的时候，我无法保证我所用的最短路为全局最短路。这个问题显著存在于floyd初期。 比如说 存在一个 ABCA 的环与一个 BCDB，其中 ( BD + DC < BC , AB + AC < BC )，而当我使 A 为固定结点，而我的 D 还不曾成为固定结点，也就不会被加入 BC 的最短路。 然而实际上并不要担心，…
昨天的多校有一道需要树Hash的基础，于是就找到了这题。这题应该算得上是树Hash的裸题了。 树Hash的方法其实十分简单。有兴趣的看一下我的这篇 博文 然而上面那片博文是定根结点的，如果根节点固定，对于树的形态进行Hash，实际上是非常简单的。 再次简单说一下树Hash的原理，对于有根树，我们Hash的是树的形态，而树的形态则有每一层的结点个数与结点所连接的相同父亲结点所决定。 因此我们对于同一层的并且是同一个父亲的结点作一个相同的Hash，那么就得到了我们要得答案。 不过也有一个简单也正确的写法，就是将同一层并且具有相同孩子结点数量作同一个Hash，也可得到我们想要的结果。 但上述方法是针对有根树而言，如果不定根，则不好判断。 这是我们可以对小数据选择枚举所有结点，对较大数据选择寻找树的重心(不会超过两个)。 下面放上题解。 2017-8-14更新： 该理论用于有根树已经被推翻，对于无根树，也就是这道题，莫名适用，也许是数据水…… 题意： 给你( n ) 棵树，每棵树用给定每个结点的父亲予以表示。问对于每一棵树，与它同构的并且序号最小的是哪一棵。…
做的第一道AC自动机非模板题，感觉真的是神了。 一些AC自动机的性质自己完全不知道…… 废话不多说，直接上题解。 题意： 给你( n )种病毒，要你求出长度为 ( m ) 的不含这 ( n ) 中病毒的数量。 思路： 这道题可以转化成图论解决，当然只能是思路而已 对于AC自动机上的每一个结点，他都可以看成是一个字符串的一部分前缀，也可以认为是一个字符串的一部分后缀。 作为一部分后缀，如果我们在一直不含病毒串的同时，长度达到了要求，我们就可以将其认为是一种可行方案。 解题关键 : 离散数学上的矩阵阶乘定理 构建一个矩阵，矩阵值 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到 ( j ) 的边数。对其求 k 次幂，所得新矩阵为 ( Mat\left[ i , j \right] ) 代表的是 ( i ) 到…
其实是道板子题………… 但是AC自动机已经学会很长时间了，当学会之后一看发现高阶的应用都得和DP相结合，还有矩阵加速呀什么什么的……就没再去碰过了 结果昨天的多校的一道中等题就是AC自动机+状压…… 有点崩溃，至今的我还是基本上只会板子……所以今天在状压写累的时候开始写一下AC自动机。 顺便小小的总结一下AC自动机模板的用法和需要注意的地方。 1. 数组大小的上限与Trie相关，上限为插入字符总数 一开始我还以为是查询字符长度 2. 如果数组下标从0开始，end对数组标记需初始化为 -1 ，一般建议全初始化为 -1 3. 格外小心字符范围，一般字母26，可见字符128，而这题的范围就是 256 因为 (2^8 ) 题意： 还是有点老套的题意。简单说就是让你找出一个网站上的病毒数量，这跟之前很多模板题是一样的…… 略有不同的是这些病毒都是经过加密的，再简单说，这个加密方式只是确定的进制转化，原本是8进制的密码，现在给你6进制形式。 思路： 只要把病毒给解码出来，就是一个模板题。 当然方法各有不同，我感觉我写的略有麻烦，建议去看kuangbin的转…