AC自动机算法详解 点击打开链接
以HDU2222 Keywords Search 为例详细讲解了AC自动机的原理和算法步骤，入门必看。
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
http://www.docin.com/p-46845432.html //英文版
//======================================================================================
http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
一. 多串匹配
。。是否出现、出现了几次、出现了哪些。。
网络流上流传最广的AC自动机模板题，问你目标串中出现了几个模式串
如果一个结点是单词末尾的话out标记为true,在search的时候对于每个结点都向fail指针找，找到out为true的就将其标记为false,且ans++
问你目标串中出现了几个模式串
同上一题，只是这题要输出模式串的ID，且字符是所有可见字符,要开[128]的儿子结点，还好没有太卡内存
目标串中各个模式串出现了几次
这就更简单了，都不用把out标记成false了~
ZOJ 3228. Searching the String
二. 自动机 DP
判定性问题、计数类问题、最优化问题
DP、状态压缩 DP、数位 DP
URAL 1158. Censored! / POJ 1625
AC自动机+DP
问你长度为N的串中不包含了模式串的串有几个
n属于1 ~ 2000000000看到这个数据范围我们就应该敏感的想到这是矩阵~
最多100个结点，先建好所有结点(不包括模式串结尾的和fail指向结尾的结点,所以其实最多只有90个有效结点)之间的转化关系，然后二分矩阵乘法，复杂度O(100^3*log(2000000000))
AC自动机+矩阵
就是不要走到尾结点上，如果和匹配串不相同的话+1dp
每个单词有val，关键需要输出路径，比较挺麻烦的，需要倒过来，如果暴力点就直接用string吧。。
大数+简单DP
位压缩，每个节点有2^10次状态，找到至少K个
HDU 4057. Rescue the Rabbit / ZOJ 3545
HDU 3962. Microgene / HOJ 3045
问你长度为1~N的串中包含了模式串的串总共有几个
上题的加强版，先要把总数26^1 + 26^2 + … + 26^N算出来，然后减去所有不包含的…反正比上题恶心一点点
答案要模2^64，直接用unsinged __int64 就OK了
Topcoder SRM 519, Div 1 Level 2
USACO 2006, November, Silver division, Round Numbers
BOJ Season Autumn, 2012, Problem B, Confusing Problem
找可以重叠和不能重叠的串个有多少，记录每个单词最后出现的pos，注意有重复的串
RE的神题，非常卡内存。。。空间复杂度(500*11^4)(这还是缩水后的，原来的是(2500*11^4))，时间复杂度要再乘上转化复杂度(4)，如果状态变化的系数高一点就过不了。。表示要非常优化的代码才能过
高中生题，做了一个小时，关键是debug一个白痴错误de了半个小时。惭愧啊。。不过这题比较好玩的是罐子基因分裂后第一个字符会消失，需要用fail指针来转移状态了
fail用来转移变短的状态，chd来转移变长的基因，同时还要记录基因的长度(长度l转移的时候需分三类讨论，l = 1，l 恰为根结点到当前结点的距离，l 大于该距离)，DP状态是100*1500[长度,结点]用滚动数组
乳鸽的神题，状态很容易看出来，有50000*1024，很难保持，我用散列表超时了，用bitset刚好可以卡过，不过后来我想，只有尾结点才有效，中间的很多结点完全可以忽略，可以先用最短路吧各个尾结点之间的距离算出来，经过测试，不到50个点，马上就优化到50*1024了，本来9s多过的优化到了100多MS
最后献上我的模板
2、Hdu 3695 Computer Virus on Planet Pandora
三. 综合问题
Tags: TSP
Tags: 状态压缩、可变进制编码
HOJ 2951. Writing Robot / HDU 3505
Tags: 最大权闭合子图
Tags: 自动机 DP、fail 指针转移
CodeChef July Challenge 2012. Favourite Numbers
Tags: 二分答案、数位 DP、构造方案
Andrew Stankevich's Contest #2, Problem A, Non Absorbing DFA
预处理、DP、高精度
SPOJ. 9941. GRE Words / HDU 4117
Tags: ????
四. Unsolved Problem .. .
... 期望问题。
... DFA 最小化 。。
... 在线构造 AC 自动机。