最近学习了AC自动机，做了notonlysuccess大牛里面的题，也该来个总结了。
AC自动机(Aho-Corasick Automaton)在1975年产生于贝尔实验室，是著名的多模匹配算法之一。
至于算法的讲解，notonlysuucess大牛极力推荐
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdfhttp://www.docin.com/p-46845432.html(上边原文地址如果无法访问的话可以访问这一个~)
我也是看着这个学习的。讲得真的挺好的。唯一的缺点就是这个pdf是英文的。不过都是简单的英文，阅读起来没有太大障碍，而且内容短小精悍。我也大力推荐这篇pdf，对于其中的out函数一定要好好理解。。。
先贴一下模板（其实就是Notonlysuccess的模板了……）
struct AC_Automaton { int fail[NODE],son[NODE][4],idx,val[NODE]; void clear() { memset(son[0],0,sizeof son[0]); idx = 1; } void insert(char *s) { int p = 0; for (; *s; ++s) { const int c = ID[(int)*s]; if (!son[p][c]) { memset(son[idx],0,sizeof son[idx]); val[son[p][c] = idx++] = 0; } p = son[p][c];//经常忘了写这句话。。 } ++val[p]; } void construct()//这边用了notonlysuccess大牛的一点优化： { for (int i = 0; i < 4; ++i) if (son[0][i]) { q.push(son[0][i]); fail[son[0][i]] = 0; } while (!q.empty()) { const int u = q.front(); q.pop();//经常忘了出队。。 for (int i = 0; i < 4; ++i) { int &v = son[u][i]; if (v) { fail[v] = son[fail[u]][i];//由于son[fail[u]]之前已经赋过值了，就可以直接赋值。 q.push(v); val[v] += val[fail[v]];//这边根据具体题目而定。 }else v = son[fail[u]][i];//这边把某个节点的儿子不一定是在trie上的真实儿子，还有可能是通过fail到达的。总之是下一个合法的儿子，这样可以省掉找fail。 } } } void dfs(int s,const int dep)//具体题目需要 { if (dep == 4) { for (int i = 0; i < idx; ++i) { if (f[i][s] == -1) continue; for (int j = 0; j < 4; ++j) if (num[j] < app[j]) if (f[son[i][j]][s + st[j]] < f[i][s] + val[son[i][j]]) f[son[i][j]][s + st[j]] = f[i][s] + val[son[i][j]]; } return; } for (int i = 0; i <= app[dep]; ++i) { num[dep] = i; dfs(s,dep + 1); s += st[dep]; } } void init()//具体题目需要 { for (int i = 0; i < idx; ++i) for (int j = 0; j < tot; ++j) f[i][j] = -1; f[0][0] = 0; } }AC;
AC自动机主要都是套上位上的DP。
每个trie上的节点都是一个状态。每一个串都只会在Trie上对应一个节点。
例题的话都是Notonlysuccess里面的了。
他都有题解和某些题目的简述。
这里提几道需要注意的题目吧。
hdu3065，这道题直接用AC做的话是可以构造数据卡T掉（如原串是AAAAAAAAAAAAAAA....,病毒是A,AA,AAA,AAAA....)这样复杂度就很高了。 改进方法是先标记最后再从trie倒着更新上去。
hdu3341,这题不用散列表，直接用状压就可以了，也就是第一位是num['A']+1进制，第二位是num['C']+1进制依此类推，记得数据范围要开到11^4
hdu3247,直接从每个源文件的节点转移就可以了，预处理出距离，然后就是一个TSP问题了(注意某个源文件是另一个的字串的情况）。
zoj3494,AC自动机+数位DP。注意处理前导0的情况。然后试了一下7k+的数位DP模板，用dfs做，在zoj竟然排到了rank2...。
转载于:https://www.cnblogs.com/lazycal/p/AC_Automaton.html
相关资源：JAVA上百实例源码以及开源项目