AC自动机是一个复杂度为O(n) 的字符串匹配算法，能够实现快速多模板串匹配。 不多BB代码在文末 如待查找串有m个，分别为
模板串： a ab abc待匹配文本
模式串： abcdcbab则能快速找到
Matching "a" in pos 0, 6 Matching "ab" in pos 0, 6 Matching "abc" in pos 0复杂度为三部分， 1、构建字典树，O(ml)，m为模板串的个数，l为模板串的平均长度。 2、构建失配链接，O(ml)。 3、文本串匹配，复杂度为O(n)，n为文本串长度。 前两个部分为离线预处理，第三部分为在线处理，实际总体复杂度为线性。
简单来说，AC自动机就是在模式串上跑字典树，指针A在模式串上跑，指针B同步在字典树上跑，A只会线性跑一次，复杂度为线性。
字典树又叫前缀树，是一个通过边来存储字符串的树。这个数据结构把前缀相同的字符串放在一起，节省空间，所以又叫前缀树。 如有6个模板串，分别为
she he say shr her yasherhs可见该串有很多部分是重复的前缀，按顺序插入字典树，则树是这个样子的
字典树不在节点存储字符，而是通过边来存储单个字符。如只会出现26个字母的话，每个节点都有26个孩子，代表出现的字符。如没有使用的孩子节点则直接为空。实心的节点则为该数据。可通过数组来实现这个过程，将字典树完全逻辑化。
typedef _Trie { char inf[MAXNODE][SIGMASIZE]; int next_node[MAXNODE][SIGMASIZE]; int value[MAXNODE]; int cnt; } Trie;其中，MAXNODE为字典树可能使用到的最大节点数量。一般以ml*来计算就足够使用了；SIGMASIZE为字符串匹配任务中可能出现的不同字符的种类数量，如26个字母任务则为26，中文匹配则为256。 next_node[i][j] 代表，i节点的第j个孩子，的节点编号。如上图中，根节点为0，其第 ‘y’ 个孩子的编号为10，则
next_node[0]['y'] = 10;实际使用中一般如下，将字符映射为数组下标。
#define index(c) ((c) - 'a') next_node[0][index('y')] = 10;如为中文则将每个文字视为2字符，每个字符映射到1~256+1中 #define index( c ) (( c ) + 129)
如上图例中字典树
next_node[5][index('r')] = 9; next_node[1][index('h')] = 2; next_node[1][index('a')] = 6; ...结构体中其余成员变量分别为 value[i]: i节点中是否具有实际数据。上图例中，实心节点的value值为1或该键值的数量，空心节点中value值为-1。（不涉及AC自动机的话，用0也行） inf[i]: i节点中的数据实体字符串。 cnt: 字典树实际使用节点数量。
for循环跑一遍模板串集就好了，每个字符串插入一遍，插入时也是for循环跑他一轮，用一个指针从root开始，在字典树上移动，遇到已存在的节点就移动，不存在的节点就cnt++开辟新的节点就好（并非真的malloc，而是逻辑开辟）。在最终节点上记录信息。
#define at(i, j) ((i) * SIGMASIZE + (j)) #define index(c) (*trie->INDEX)(c) /***************************************************************** * Type name: Trie字典树 * Parameter: next_node[i][j]: i节点的第j儿子的编号 * inf_id[i]: i节点的信息对应外部字符串的编号 * value[i]: i节点是否有信息/相同信息的个数 * size: 字典树实际使用节点数 * MAXNODE: 字典树可使用节点数上限 * SIGMASIZE: 每个节点的儿子数量 * INDEX: 函数指针，传入字符映射关系 * Function: Trie_init: 字典树初始化，需要传入字典树实例、开 * 辟节点个数、容许出现的字符种类数量、 * 字符映射关系回调函数 * Trie_insert: 插入字符串，需要传入字典树实例、待插 * 入字符串、该字符串在模板集中的编号 * Trie_destroy: 析构函数，清理内存。 ****************************************************************/ typedef struct _Trie { int *value; int *inf_id; int *next_node; int size; int MAXNODE; int SIGMASIZE; int (*INDEX)(char); } Trie; int Trie_init(Trie *trie, int MAXNODE, int SIGMASIZE, int (*INDEX)(char)) { int i = 0; trie->size = 1; //初始有1个root节点，编号为0 trie->MAXNODE = MAXNODE; trie->SIGMASIZE = SIGMASIZE; trie->INDEX = INDEX; /* 使用一维数组来实现二维数组 */ trie->next_node = (int *)malloc(sizeof(int) * MAXNODE * SIGMASIZE); trie->inf_id = (int *)malloc(sizeof(int) * MAXNODE); trie->value = (int *)malloc(sizeof(int) * MAXNODE); for (i = 0; i < SIGMASIZE; i++) { trie->next_node[at(0, i)] = -1; } trie->value[0] = -1; return 0; } int Trie_insert(Trie *trie, char *str, int id) { int c = 0; int i = 0, j = 0; int now = 0; int len = strlen(str); int SIGMASIZE = trie->SIGMASIZE; int *next_node = trie->next_node; int *value = trie->value; int *inf_id = trie->inf_id; for (i = 0; i < len; i++) { c = index(str[i]); if (next_node[at(now, c)] < 0) { next_node[at(now, c)] = trie->size; for (j = 0; j < SIGMASIZE; j++) next_node[at(trie->size, j)] = -1; value[trie->size] = -1; //中间节点权值为-1 trie->size++; } now = next_node[at(now, c)]; } /* 这部分决定是否去重 */ if (value[now] < 0) value[now] = 1; else value[now]++; inf_id[now] = id; return 0; } int Trie_destroy(Trie *trie) { CHECK_NULL_POINTER(trie); if (NULL != trie->next_node) free(trie->next_node); trie->next_node = NULL; if (NULL != trie->value) free(trie->value); trie->value = NULL; if (NULL != trie->inf_id) free(trie->inf_id); trie->inf_id = NULL; return 0; }使用
int ind(char c); inline int ind(char c){ return c - 'a'; } int main() { Trie trie; Trie_init(&trie, 100, 26, ind); Trie_insert(&trie, "she", 0); Trie_insert(&trie, "he", 1); Trie_insert(&trie, "say", 2); Trie_insert(&trie, "shr", 3); Trie_insert(&trie, "her", 4); Trie_destroy(&trie); }字典树构建完成。 字典树既可以做前缀树，也可以做后缀树，应在合适的时候选择合适的存储方法。
AC自动机实际上是对字典树的拓展，一般来说字典树的空儿子节点均为-1或者0，经过AC自动机的构建，空儿子节点可以去到，另一个模板串前缀与当前已达节点的后缀相同的节点。 例如三个模板串分别为abc、bc、c，那么当文本中匹配到了abc的时候，理应认为同样匹配到了bc和c。即当前已匹配部分具备另一个模板串的前缀。
考虑匹配一个模板串abc，模式串abd，暴力算法在匹配时会一个个的去对比： 模式串找到a，模板串找到a，匹配 模式串找到b，模板串找到b，匹配 模式串找到d，模板串找到c，不匹配 当遇到不匹配的时候，整个匹配过程又要从头开始，浪费时间。在字典树上的表现则是，now指针从root根节点开始，经过匹配，会走到树枝上，失配时，会直接回到根节点从头开始匹配。 而AC自动机则是构建失配链接，使得当找到d失配的情况下，能够直接快速跳转到以d为前缀的字符串的节点上。 例
模板串 she he say shr her 待匹配模式串 sshs当读取到第一个s时，now指针从0节点走到1节点。 当读取到第二个s时，此时失配，没有任何模板串有ss前缀。则此时now指针应该仍处在1节点，其next_node[1][‘s’] = 1，因为ss已匹配后缀等于模板串的前缀，已经走过的路不应该重复走。 读取第三个字符h，now指针从1走到2。 读取第四个字符s，失配，但是匹配前缀s。now回到1。
同理，当走到3节点时，如遇到一个r，则应跳转至9节点。
只有当前后缀和任何前缀都不匹配时，才跳转回根节点。 完整构建AC自动机，则会得到一个比较复杂但是字典树的每个节点的子树都比较有用的 字典树。 上图模板集经过AC自动机构建，将变为下图的样子，实际则更为复杂。
红蓝绿线分别为第1、2、3层跳转关系。
首先增加一个失配链接fail数组，该数组指明当now处在i号节点时，如此时失配，跳转到fail[i]节点位置，然后再次进行匹配操作。fail数组是一个中间变量，构建AC自动机时使用，构建完成则不再使用。
失配链接的本质是，如果一个点i的fail指针指向j，那么root到j的字符串（前缀）是root到i的字符串的一个后缀。
如，根节点为第0层，由于第一层仅匹配了一个字符，任何字符都是自己的前缀，所以第一层所有的fail指针均指向根节点。当在第一层失配时，则回到根节点再次匹配。
next_node[now][i] = next_node[ fail[now] ][i];比如now处在1节点，此时又遇到s，则next_node[1][‘s’] = next_node[root][‘s’]; 匹配了的字符则继续往字典树下层走。 通过失配链接，则可以把下层的失配回流到上层某层重新进行匹配，而不是直接回到根。
在往下层走的同时，下层的失配链接等于当前节点失配时重新匹配的节点
fail[ next_node[now][i] ] = next_node[ fail[now] ][i];fail[ next_node[1][‘h’] ] = next_node[ fail[1] ][‘h’] fail[2] = next_node[0][‘h’] fail[2] = 4 可见当在2号点失配时，则默认匹配了h，跳转到4号点继续运行。
具体方式通过广搜来构建，从第0层逐层向下递推。当走到某层的时候，该层的所有链接都已在上一层推出。推到底时，则AC自动机构建完成。 代码如下
首先在字典树数据结构中加入两个成员
typedef struct _Trie { /* 字典树成员变量 */ int *value; int *inf_id; int *next_node; int size; int MAXNODE; int SIGMASIZE; int (*INDEX)(char); /* AC自动机成员变量 */ int *fail; int *last; } Trie; int Aho_corasick_build(Trie *trie) { CHECK_NULL_POINTER(trie); int i = 0; Queue que; Queue_init(que, trie->MAXNODE); int SIGMASIZE = trie->SIGMASIZE; int *next_node = trie->next_node; int *value = trie->value; int *inf_id = trie->inf_id; trie->fail = (int *)malloc(sizeof(int) * trie->MAXNODE); CHECK_NULL_POINTER(trie->fail); trie->last = (int *)malloc(sizeof(int) * trie->MAXNODE); CHECK_NULL_POINTER(trie->last); int *fail = trie->fail; int *last = trie->last; fail[0] = 0; for (i = 0; i < SIGMASIZE; i++) { if (next_node[at(0, i)] == -1) next_node[at(0, i)] = 0; //回到根节点 else { fail[ next_node[at(0, i)] ] = 0; Queue_push(que, next_node[at(0, i)]);//广搜将第一层入队 } } while (!Queue_empty(que)) { int now = Queue_top(que); Queue_pop(que);//printf("\nnow=%d\n", now); for (i = 0; i < SIGMASIZE; i++) { if (next_node[at(now, i)] == -1) next_node[at(now, i)] = next_node[at( fail[now] , i)]; else { fail[ next_node[at(now, i)] ] = next_node[at(fail[now], i)]; Queue_push(que, next_node[at(now, i)]); //后缀链接。如果要去的是单词节点，last[下一个]就指向那个单词节点。 //否则指向上一层的那个，直至根节点。 if (value[ fail[ next_node[at(now, i)] ] ] > 0) last[ next_node[at(now, i)] ] = fail[ next_node[at(now, i)] ]; else last[ next_node[at(now, i)] ] = last[ fail[ next_node[at(now, i)] ] ]; } // if (next_node[at(now, i)] > 0) // printf("next[%d][%c]=%d last[%d]=%d\n", now, i + 'a', next_node[at(now, i)], now, last[now]); } } Queue_destroy(que); return 0; }代码中的last链接为后缀链接。如匹配到abc时，应认为bc、c均匹配成功。last[abc]=bc, last[bc]=c按顺序向上层映射，当找到某个词时，递归地向上查找即可拿到所有的和改词后缀相同的词。 构建结果，SIGMASIZE中未输出的都是直接跳转到根节点，为0
now=0 next[0][h]=4 last[0]=0 next[0][s]=1 last[0]=0 now=4 next[4][e]=5 last[4]=0 next[4][h]=4 last[4]=0 next[4][s]=1 last[4]=0 now=1 next[1][a]=6 last[1]=0 next[1][h]=2 last[1]=0 next[1][s]=1 last[1]=0 now=5 next[5][h]=4 last[5]=0 next[5][r]=9 last[5]=0 next[5][s]=1 last[5]=0 now=6 next[6][h]=4 last[6]=0 next[6][s]=1 last[6]=0 next[6][y]=7 last[6]=0 now=2 next[2][e]=3 last[2]=0 next[2][h]=4 last[2]=0 next[2][r]=8 last[2]=0 next[2][s]=1 last[2]=0 now=9 next[9][h]=4 last[9]=0 next[9][s]=1 last[9]=0 now=7 next[7][h]=4 last[7]=0 next[7][s]=1 last[7]=0 now=3 next[3][h]=4 last[3]=5 next[3][r]=9 last[3]=5 next[3][s]=1 last[3]=5 now=8 next[8][h]=4 last[8]=0 next[8][s]=1 last[8]=0可对比字典树的例图，可见构建成功。其中last[3]=5则代表，3节点的she，其后缀具有5节点的he，即3词的后缀完整包含5词。
运行起来就轻松了。进入find函数去跑，因为整个字典树已经构建成闭环，遇到任何字符都可以直接在树上跑。 然后每个字符检查一下该节点是否有键值（value是否为1），如果有键值就进入递归打印阶段 递归打印阶段中，通过后缀链接递归地向上层找，直至根节点。（找到abc应认为找到了bc和c） 最终结果通过队列或者什么数据结构带出即可。
int recursion_print(Trie *trie, int now, int i, Queue *res) { if (now > 0) if (trie->value[now] > 0) { int tmp = trie->value[now]; Queue_push(*res, i); Queue_push(*res, trie->inf_id[now]); // trie->value[now] = 0; //1、 tmp += recursion_print(trie, trie->last[now], i, res); // trie->last[now] = 0; //2、这两行决定查找到的模板是否重复计算 return tmp; } return 0; } int Aho_corasick_find(Trie *trie, char *txt, Queue *res) { CHECK_NULL_POINTER(trie); CHECK_NULL_POINTER(txt); int len = strlen(txt); int sum = 0, i = 0; int now = 0; int SIGMASIZE = trie->SIGMASIZE; int *next_node = trie->next_node; int *value = trie->value; int *inf_id = trie->inf_id; int *last = trie->last; for (i = 0; i < len; i++) { int ch = index(txt[i]); now = next_node[at(now, ch)]; if (value[now] > 0) sum += recursion_print(trie, now, i, res); else if (last[now] > 0) sum += recursion_print(trie, last[now], i, res); } return sum; }如对上文提及的模板串集去跑"shesay"这个模式串，则可得到
shesay In pos 2 get string[0]:she In pos 2 get string[1]:he In pos 5 get string[2]:say完整c版代码如下，上节代码中使用的队列在头文件中有实现。 https://download.csdn.net/download/aaddggddaa/12910824
