【字符串_AC自动机专辑】
在acm用到的算法中我觉得字符串类算法在实际中的应用价值可能最大，因为我们很多时候在和字符串打交道，在和匹配、查询打交道，比如我们按Ctrl+F的查找，目测有用Kmp匹配算法，linux下的fgrep利用AC自动机实现，还有很多的哈希方法也在各种实际应用中展现它的价值等等。
本文针对AC自动机做个总结，并附带若干题解。
建立AC自动机的一般步骤是:1、初始化根节点，根节点是所有字符串的前缀 2、利用模式串建立字典树(一般将主串叫匹配串，子串或去匹配的串叫模式串) 3、对字典树上的构建fail指针，fail指针指向当前串的最长后缀，这个后缀也是某个串的前缀，和KMP的next指针相似 4、利用构建好的ac自动机或者trie图(ac自动机的所有后继节点拓展之后就是trie图)进行操作，一般有查询、利用trie图建立矩阵、利用trie图进行状态DP等等。
AC自动机（以下trie图也叫AC自动机)的精华是fail指针，上面有颜色的字是对fail指针的阐释，当匹配到p这个节点，如果后继节点失配了，那么总是找当前串的最长后缀也是某串的前缀的的后继节点去匹配，如果还不匹配继续找p->fail的最长后缀的后继结点去匹配，直到遇到能匹配的后继结点或者回溯到根节点重头再来。
在字典树上构建fail指针是通过一个广搜来完成，从根节点开始像洪水般一层层向外构建fail指针，规定根节点的fail指针指向它自己。假设p点fail指针构建好了，q是p的后继结点也就是说q = p->next[k],除根为的所有节点都有q->fail = p->fail->next[k] ，特别的，当p是根时p->next[k]->fail = root,显然根的第k个后继没办法匹配不可能再指向第k个后继，否则就陷入死循环.具体的过程见我的Hdu 2222代码。
再说下如何将ac自动机改造成trie图，其实只需要一步就完成了。当我们匹配到p这个节点，如果它的后继节点失配了，ac自动机的做法是顺着fail指针一步一步回溯直到某点的后继结点匹配之或者到达根节点，而trie图就将这步改成O(1)的做法，最后匹配的那个节点直接赋给p的后继节点p->next[k].因为我们是一层层向外扩散，到达节点p，p->fail的next数组都已经赋好值，可以直接利用..这达到的效果正和fail指针的定义相一致。
题目列表：
1、 Hdu 2222 Keywords Search
2、Hdu 3695 Computer Virus on Planet Pandora
3、Poj 4052 Hrinity (金华邀请赛I)
4、Spoj 7758. Growing Strings
5、Hdu 4417 GRE Words
6、Spoj 1676. Text Generator
7、Hnu 10104 病毒
8、9、10、11...持续更新
Hdu 2222 Keywords Search
模版题，普通的AC自动机照样不超时，但这题的数据太弱，很多人写搓了但是还能ac，最下面我附上本题的代码，并且带一些坑爹数据。
Hdu 3695 Computer Virus on Planet Pandora
题目数据看上去很大，其实不然，用ac自动机可以轻松虐。先用模式串构建ac自动机，然后将主串解析成正常字符串，正反各查询一次就好了。
Poj 4052 Hrinity (金华邀请赛I)
上题的加强版。但模式串不能出现某串是另一串的子串。本题要用到fa指针和fail指针，一个找当前串前缀一个找后缀，从从当前串的结束节点开始沿着fa指针和fail指针遍历到根节点，这两条路径上的节点到根节点的串便是当前串的子串，然后进行相应地处理即可。详细报告和测试数据见Here.
Spoj 7758. Growing Strings
估计这题是2011年成都区域赛GRE那题的原题，但这题比较简单。题目给定n个字符串，让我们找出若干个字符串组成一个序列，前面一个字符串是后面一个字符串的子串，问我们能获得得最长序列的长度。因为先坐GRE那题，受那题思维束缚，死活要让这题的字符串从短到长，然后顺序就固定了，这样就按照GRE那题的做法，先离线建立ac自动机，然后一步步查询，然后就跪了。其实没要求顺序，本题就变得十分简单，我们要做的是找某个串的匹配部分和fail指针指向的最长后缀，取其中大者作为前序状态进行转移即可。这步在我们构造trie图的时候就可以边构造fail指针边进行转移。
Hdu 4417 GRE Words
2011年成都区域赛的题目，是上题的加强版，先建立ac自动机但不更新节点信息，构建完成之后进行查询、更新。具体报告见Here。
Spoj 1676. Text Generator
题目给定n个熟悉的串，问长度为m且至少含一个熟悉串的方案数，m<=100万。逆向思维，用总的方案数减去不含熟悉串的方案数。先用ac自动机先求出一个矩阵，mat[i][j]表示从自动机的节点i不经过熟悉串的结尾有几种方法可以走到节点j。然后用mat矩阵进行二分快速幂，幂乘的时候注意尽量少用%mod。
Hnu 10104 病毒
题目给定n个病毒串，问是否存在一个无限循环串都不包含这n个串。这题困扰了我很多天，我在建好AC自动机后尝试过很多解法，比如判断能不能回到根节点、将将两个相同的病毒串拼起来然后做n次插入等等，卡了好几天，不过我觉得这样挺好的，至少我的思维没被束缚。
这题的本质是找到一个环，环上不包含所有的病毒串。正解是先构建AC自动机，改造成trie图，然后在trie图上顺着next数组进行深搜，如果搜到的一个节点在之前搜过，说明出现了环，否则就不存在这样的环。
Hdu 2222 模版
#include <stdio.h>#include <string.h>#include <iostream>using namespace std;#define MIN 11000#define MAX 510000struct node {int cnt,flag;node *next[26],*fail;}tree[MAX],*root,*qu[MAX];int n,ans,ptr,head,tail;char str[MAX*2],dir[60];node *CreateNode() {for (int i = 0; i < 26; ++i)tree[ptr].next[i] = NULL;tree[ptr].fail = NULL;tree[ptr].cnt = tree[ptr].flag = 0;return &tree[ptr++]; }void Initial() {ans = ptr = 0;head = tail = 0;root = CreateNode();}void Insert(char *str) {int i = 0,k;node *p = root;while (str[i]) {k = str[i++] - 'a';if (p->next[k] == NULL)p->next[k] = CreateNode();p = p->next[k];}p->cnt++,p->flag = 1;}void Build_AC() {qu[head++] = root;while (tail < head) {node *p = qu[tail++];for (int k = 0; k < 26; ++k)if (p->next[k]) {if (p == root) p->next[k]->fail = root;else {p->next[k]->fail = p->fail->next[k];if (!p->next[k]->flag) p->next[k]->cnt = 1;//象征性地表示以当前点的所有后缀是否有危险节点}qu[head++] = p->next[k];}else {if (p == root) p->next[k] = root;else p->next[k] = p->fail->next[k];}}}int Query(char *str) {node *p = root;int i = 0,k,cnt = 0;while (str[i]) {k = str[i++] - 'a';p = p->next[k];if (p->cnt) {node *temp = p;while (temp != root) {if (temp->flag) cnt += temp->cnt;temp->cnt = 0,temp = temp->fail;}}}return cnt;}int main(){int i,j,k,t;scanf("%d",&t);while (t--) {scanf("%d",&n);Initial();for (i = 1; i <= n; ++i)scanf("%s",dir),Insert(dir);Build_AC();scanf("%s",str);ans = Query(str);printf("%d\n",ans);}}Hdu 2222 数据：
Input:53bbacabcdabcba4abcdbcdecddabcde2sherheshe2sherhesher6abcabcabcbcaabcaabcaaaaaaaaaabcbcccccOutPut:14125