AC自动机

AC自动机--周煜焜AC自动机Aho-Corasickautomaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。----摘自百度百科重点来了AC自动机不是Accept自动机由刚才百度百科可知AC自动其实是Trie树构建的构成的DAG(有向无环图)AC自动机是DFA(有穷状态自动机)所以状态转移也是其精髓所在(等学完矩阵连乘可以体会一下poj2778等)由其构造方法可知算法是O(n)时间的多模式串匹配Trie树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。----摘自百度百科Trie简介Trie树是一个CH叉树，CH是字符集大小构造Trie树示例代码(trie.cpp)Trie树节点structnode{node*go[CH];intval[CH];};当然也可以用数组模拟：intch[NODE_MAX][CH],val[NODE_MAX];intsz;举个栗子！假设以串：heshehishers构造Trie树可以得到下图请先假设这个图上只有那个根节点好不好--有了↓ch[0][h]=1插入he有了↓ch[0][h]=1ch[1][e]=2插入he有了↓ch[0][h]=1val[2]=1ch[1][e]=2插入hech[0][h]=1val[2]=1ch[1][e]=2ch[3][h]=4ch[0][s]=3ch[4][e]=5val[5]=2ch[1][i]=6ch[6][s]=7val[7]=3ch[2][r]=8val[9]=4ch[8][s]=9插入其他串(最终形态!)hdu1671hdu1075hdu1251hdu1247AC自动机最原始的AC自动机就是加入了类似KMPnext数组的失配指针失配指针指向另一个点成为一个新的边其实求失配指针的方法很多(窝见过的就有三四种--||)示例代码(DFA.cpp)用的是《刘汝佳的算法竞赛入门经典训练指南》上的最简单的方法为了熟悉失配指针的匹配可以按照代码把失配指针画出来while(rear!=front){intcur=*front++;for(intc=0;cCH;c++){intu=ch[cur][c];intfail=f[cur];if(u){while(fail&&!ch[fail][c])fail=f[fail];f[u]=ch[fail][c];last[u]=val[f[u]]?f[u]:last[f[u]];*rear++=u;}}}注：last[]:因为同一个节点可能对应多个单词结尾所以我们需要沿着失配边往回走为了提高效率这里增设一个指针last[]它指向失配时遇到的下一个单词节点hdu2222hdu2896hdu3065zoj3228