最近学习了AC自动机，做了notonlysuccess大牛里面的题，也该来个总结了。
AC自动机(Aho-Corasick Automaton)在1975年产生于贝尔实验室，是著名的多模匹配算法之一。
至于算法的讲解，notonlysuucess大牛极力推荐
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf
http://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…。
