ac自动机基础入门
- 格式：ppt
- 大小：4.47 MB
- 文档页数：24
下载文档原格式
合集下载
编译原理第三章 自动机基础(1)
…
接受空串的 FA的典型特征！
Ⅱ.第二条通路：FA2
+ ① => ①
∴ L(FA1)={ abnc| n≥0 }
b + ① => ④
bb + ① => ④ => ④
…
因而
∴ L(FA2)={ bn| n≥0 }
∴ L(FA)={abnc, bn| n≥0}
3.2.3 有限自动机的两种表现形式
【例3.6】有限自动机 ：FA=( Q,∑,S,F, ) 其中: Q={1,2,3,4},∑={a,b,c}, S={1,2}, F={3，4}
9.
={abn|n≥0}
10.7. L((a|b)*)= (L(a|b))*={a,b}*
11. 即:由a,b组成的所有符号串(包括空串)集合。
➢基本图形库
=+>
.=+>
=.+ℓ>
=+ℓ>
A
P: E T
F
T | E +T | E -T F | T *F | T /F i|( E )
=>*, =>+ , =>.* , =>.+ , =>l* , =>l+ , =>.l+ ，=>.l*
如 右图有限自动机：
则 L(FA)的 识别过程如下所
+- ①
a b
b ②
c
b
③-
示：
④-
※ L(FA)的生成(或识别)过程示例：
Ⅰ.第一条通路：FA1 ac
+ ① => ② => ③
+- ①
接受空串的 FA的典型特征！
Ⅱ.第二条通路：FA2
+ ① => ①
∴ L(FA1)={ abnc| n≥0 }
b + ① => ④
bb + ① => ④ => ④
…
因而
∴ L(FA2)={ bn| n≥0 }
∴ L(FA)={abnc, bn| n≥0}
3.2.3 有限自动机的两种表现形式
【例3.6】有限自动机 ：FA=( Q,∑,S,F, ) 其中: Q={1,2,3,4},∑={a,b,c}, S={1,2}, F={3，4}
9.
={abn|n≥0}
10.7. L((a|b)*)= (L(a|b))*={a,b}*
11. 即:由a,b组成的所有符号串(包括空串)集合。
➢基本图形库
=+>
.=+>
=.+ℓ>
=+ℓ>
A
P: E T
F
T | E +T | E -T F | T *F | T /F i|( E )
=>*, =>+ , =>.* , =>.+ , =>l* , =>l+ , =>.l+ ，=>.l*
如 右图有限自动机：
则 L(FA)的 识别过程如下所
+- ①
a b
b ②
c
b
③-
示：
④-
※ L(FA)的生成(或识别)过程示例：
Ⅰ.第一条通路：FA1 ac
+ ① => ② => ③
+- ①
AC自动机构造
构造失败指针例图
• 首先root的fail指针指向NULL，然后root入队，进入循环。第1次 循环的时候，我们需要处理2个节点：root->next[‘h’-‘a’](节点h) 和 root->next[‘s’-‘a’](节点s)。把这2个节点的失败指针指向root ，并且先后进入队列，失败指针的指向对应上图中的(1)，(2)两条 虚线； • 第2次进入循环后，从队列中先弹出h，接下来p指向h节点的fail 指针指向的节点，也就是root；进入第13行的循环后，p=p->fail 也就是p=NULL，这时退出循环，并把节点e的fail指针指向root ，对应上图中的(3)，然后节点e进入队列； • 第3次循环时，弹出的第一个节点a的操作与上一步操作的节点e 相同，把a的fail指针指向root，对应上图中的(4)，并入队； • 第4次进入循环时，弹出节点h(图中左边那个)，这时操作略有不 同。在程序运行到14行时，由于p->next[i]!=NULL(root有h这个 儿子节点，图中右边那个)，这样便把左边那个h节点的失败指针 指向右边那个root的儿子节点h，对应上图中的(5)，然后h入队。 • 以此类推：在循环结束后，所有的失败指针就是上图中的这种形 式。
1 int query(node *root){ 2 int i=0,cnt=0,index,len=strlen(str); 3 node *p=root; 4 while(str[i]){ 5 index=str[i]-'a'; //index=0~26 6 while(p->next[index]==NULL && p!=root) p=p->fail; //p指向p的失败指针所指向的节点 7 p=p->next[index]; //p指向index节点 8 p=(p==NULL)?root:p; 9 node *temp=p; 10 while(temp!=root && temp->count!=-1){ 11 cnt+=temp->count; //节点信息为1时，cnt+1， 12 temp->count=-1; //将count信息置为-1，表示已经出现过了 13 temp=temp->fail; //temp指向e的失败指针说指向的节点继 续查找 14 } 15 i++; 16 } 17 return cnt; 18 }
自动机入门——AC自动机
⾃动机⼊门——AC⾃动机AC ⾃动机1 算法简介AC ⾃动机是⼀个以 Trie 为基础结合 KMP 的思想建⽴的。
在 AC ⾃动机中，每⼀个状态代表着某个模式串的前缀，⽽整个 DFA 的结构其实是所有模式串的Trie 树。
⽽ AC ⾃动机可以处理这样⼀个问题：多模式匹配。
即给你若⼲个模式串和⼀个主串，要求我们对每⼀个字符串和主串进⾏匹配。
我们肯定不能做多次 KMP，所以我们有了 AC ⾃动机。
2 算法讲解2.1 状态设计struct node{int ch[26],end,fail;};其中，ch 数组是 Trie 树的指针，end 是判断这个状态为多少串的节点，fail 指针是后缀链接，指向最长真后缀对应的状态。
⽐如这个动图（其中的黄线是后缀链接）：其中 2 节点的指针画错了，应该是指向 0。
2.2 插⼊因为⾃⾝结构就是 Trie 的结构，所以 AC ⾃动机的插⼊和 Trie 树的插⼊是⼀模⼀样的。
代码：inline void insert(char *s){int now=0,len=strlen(s);for(int i=0;i<len;i++){int k=s[i]-'a';if(!p[now].ch[k]) p[now].ch[k]=++tot;now=p[now].ch[k];}p[now].end++;}2.3 建⽴在这⾥，我们需要建⽴ AC ⾃动机，Trie 树已经建好了，我们的⽬的是构建失配指针 fail 。
暴⼒构建的话就是取其⽗节点，然后不断跳 fail ，直到调到⼀个状态，它有⼀条有相同字符的出边。
但是这样时间复杂度不优，怎样优化？我们先上代码：inline void build(){queue<int> q;for(int i=0;i<26;i++) if(p[0].ch[i]) q.push(p[0].ch[i]);while(q.size()){int top=q.front();q.pop();for(int i=0;i<26;i++){if(p[top].ch[i]) p[p[top].ch[i]].fail=p[p[top].fail].ch[i],q.push(p[top].ch[i]);else p[top].ch[i]=p[p[top].fail].ch[i];}}}这⾥我们通过对跳 fail 的路径进⾏压缩，如果⼦节点存在，那就好说，我们把 fail 直接连过来就可以，但是如果不存在，我们就采⽤路径压缩，把其 fail 的⼦节点连过来，这样就完成了路径压缩。
AC自动机
3. output函数out(q)：输出在状态q时，所有匹配的模式串
• Example：依次插入模式串"he","she","his","hers"，构建出的各个结点 序号的顺序如下，虚线表示fail指针（状态0没有），橙色结点是模式 串的结束，旁边有output函数的输出值，注意output(5)={"she","he"}
如果所有可能出现的字符的集合∑是固定的，则阶段一的时间复杂度为 O(n)，n=|p1|+...+|pk| 阶段二 用BFS顺序遍历trie树的结点，遍历过程中计算结点的fail和output 函数，伪代码：
Q = emptyQueue(); for ( a ∈ ∑ ) if ( (q = g(0, a)) != 0 ) { f(q) = 0; //根结点下的第一层结点的fail指针都指向根结点 Q.push(q); } while ( !Q.empty() ) { r = Q.pop(); for ( a ∈ ∑ ) if ( (u = g(r, a)) != Φ ) { Q.push(u); v = f(r); while ( g(v, a) == Φ ) v = f(v); f(u) = g(v, a); out(u) += out( f(u) ); } } 阶段二的复杂度可看成是BFS的，所以也是O(n)
– 如果在pi中的字符结束之前，路径就终止了，那么为pi中剩余的所有字符创建新 的边和结点 – 在pi结束的时候，记录一下当前的结点为模式串pi的终止结点
• 构建的时间复杂度为O(|p1|+...+|pk|)=O(n)
keyword tree：查找
AC算法学习笔记
AC算法学习笔记1、算法流程图（1） void Init()此函数是初始化函数，⽤来给fail数组和goto数组初始化值。
（2） void GotoFunction(string x)这个函数的作⽤是⽣成有限⾃动机状态转移图。
(3) void FailFunction(int target,int k)这是fail函数，核⼼内容是求出每个状态的fail值。
(4) void UpdateOutput()这是update输出函数。
其作⽤是更新每个状态的输出值。
（5）void Check(string x)这个是check函数，其作⽤是判断改状态下output函数是否有输出，如果有输出就输出相应状态下的字符串。
并且决定该状态接受输⼊之后的去向，如果fail，则调⽤该状态的fail 函数来决定去向。
（6）int main()主函数，整个过程的⼊⼝。
2、⾃动机所定义的数据结构及其功能（1） int Goto[M][26];goto数组是状态机状态的载体，内部存储着本次实验的全部状态。
起始状态为0，之后每获得⼀个有效输⼊就⽣成⼀个新的状态。
但是在⽣成状态之前要进⾏检验，看是否已经存在本次状态。
（2） int Fail[M];fail数组存储的是该状态获得输⼊后，如果结果为fail之后的转向状态。
（3） string Output[M];output数组是⼀个字符串数组，存储的是以该状态为终结状态的字符串。
当然，字符串不唯⼀，AC算法的核⼼任务之⼀就是找到每个状态为终结状态时候的全部输出字符串。
（4） string Depth[M];depth数组⽤来标⽰该状态在第⼏层。
我们在此次实验中将goto函数创建的状态看作⼀个树，因此必然需要⼀个数组来指明树中的节点所在的层数。
3、转向函数、失效函数、输出函数的构建过程（1）转向函数我们⾸先来看其伪代码：结合伪代码和刚才的函数流程图，我们可以看出转向函数⾸先对数组进⾏初始化。
字符串多模匹配算法之AC自动机理解心得
字符串多模匹配算法之AC自动机理解心得AC自动机算法全称Aho-Corasick算法，是一种字符串多模式匹配算法。
用于在一段文本中查找多个模式字符串。
最近看到这个算法的一些文章，由于理解能力有限，琢磨了许久才有一些眉目，故记下此时的理解过程，防止过久了又要琢磨许久才能理解，也希望能帮助其他人加深理解，如有理解不当之处还望指出修正。
^_^总结如下：该算法有两个主要步骤，一个是字典树的构造，一个是搜索路径的确定。
1. 字典树的构造这个比较好理解，就是把要匹配的一些字符串添加到树结构中去，树边就是单词中的字符，单词中最后一个字符的连接节点添加标志，以表示改节点路径包含1个字典中的字符串，搜索到此节点就表示找到了字典中的某个单词，可以直接输出。
例子：某字典P=｛he,she,his,hers｝对应的字典树如下图：图中有数字的节点到根节点的路劲正好对应字典中的字符串，数字表述单词在字典中的顺序，也可以是其他标志。
【转载请注明出处：/absolute8511/blog/item/73ffcbf293d86e14b17ec5e9.html】2. 搜索路径的确定就是这部分我琢磨了很久，我的理解是利用后缀字符串来确定。
后缀字符串就是某个字符串的后面的一部分。
比如abcde的后缀字符串有bcde,cde,de和e。
假定目标字符串为ushers，字典为上图所示。
搜索过程目标字符串指针指向的字符和字典中的字符会有以下几种情况：a. 当前字符匹配，表示从当前节点沿着树边有一条路径可以到达目标字符，此时只需沿该路径走向下一个节点继续匹配即可，目标字符串指针移向下个字符继续匹配；如：当指针指到s处，此时字典树指针处于根，要从根到s处，可以看到图中有一条从根经s连接到的节点，因此字典树节点指针指向此节点，目标字符串指针移动到下一字符h继续匹配；显然当前节点有一条经h连接到的节点，于是重复操作到有数字标志的节点2处，表示已找到，该匹配字符串就是"she"，输出该字符串的位置后，目标字符串指针增1指向"r"，字典指针指向数字2节点，进行下次匹配。
一个自己编写的简单AC自动机代码-----ACautomataget√
⼀个⾃⼰编写的简单AC⾃动机代码-----ACautomataget√最近⼀直在优化项⽬中字符串匹配的问题，于是就想起了⾃动机，之前也看过⼀些⽂章，⼀直没有实现，现在项⽬中要⽤，然后⼜看了⼀些关于AC⾃动机的⽂章，这⾥实现了⼀个简单的AC⾃动机的⼩接⼝，我是实现⾃动机状态结构采⽤了trie树，实现起来简单⼀些，但在⼀定程度上造成空间复杂度的增加，欢迎⼤家纠错和⼀起交流经验,下⾯是代码。
1 #include <stdio.h>2 #include <stdlib.h>3 #include <string.h>45#define CHAR_EXTERN 26 //trie的next指针的最⼤数⽬,全字符时应设置为256然后和0xff进⾏&运算67 typedef struct ac_node ac_node;8 typedef struct ac_node* ac_node_p;910#define QUEUE_TYPE ac_node_p //进⾏此宏定义,就可以把queue封装成接⼝使⽤11#define FREE_QUEUE_VALUE //queue->value为动态申请内存需要做此操作1213int queue_node_num = 0;1415//定义队列结构⽤于计算失效指针16 typedef struct queue_node17 {18 QUEUE_TYPE value;19struct queue_node *next;20 }queue_node;212223 typedef struct queue24 {25 queue_node *head;26 queue_node *tail;27 }queue;2829/*30 * queue创建结点31*/32 queue_node *queue_build_node(QUEUE_TYPE value)33 {34 queue_node *node = (queue_node *)malloc(sizeof(queue_node));3536if(node == NULL)37 {38 #ifdef AC_DEBUG39 printf("queue node bulid error memory is full !!\n\n");40#endif41return NULL;42 }4344 node->value = value;4546 node->next = NULL;4748return node;49 }5051/*52 * queue初始化53 * return -1 失败 else 成功54*/55 queue *queue_init()56 {57 queue *ac_queue = (queue *)malloc(sizeof(queue));5859if(ac_queue == NULL)60 {61 #ifdef AC_DEBUG62 printf("queue build failed memory is full\n\n");63#endif64return NULL;65 }6667 ac_queue->head = ac_queue->tail = queue_build_node(NULL);6869if(ac_queue->head == NULL)70 {71 #ifdef AC_DEBUG72 printf("queue build head error memory is full\n\n");73#endif74return NULL;75 }77//ac_queue->head->next = ac_queue->tail;7879return ac_queue;80 }8182/*83 *queue 为空判断84 *return 1 为空 0 不为空85*/86int queue_is_empty(queue *ac_queue)87 {88if(ac_queue->head == ac_queue->tail)89 {90return1;91 }9293return0;94 }9596/*97 * queue 向队尾添加结点98*/99void queue_insert(queue *ac_queue,queue_node *node)100 {101 ac_queue->tail->next = node;102 ac_queue->tail = node;103 queue_node_num++;104 #ifdef AC_DEBUG105 printf("after insert the queue node num is %d :\n",queue_node_num);106#endif107 }108109/*110 *queue 提取队⾸结点value值111*/112 QUEUE_TYPE queue_first(queue *ac_queue)113 {114if(queue_is_empty(ac_queue))115 {116 #ifdef AC_DEBUG117 printf("the queue is empty can not return head!!\n");118#endif119return NULL;120 }121122return ac_queue->head->next->value; //队⾸不存值,从队⾸的下⼀个结点开始取值123 }124125/*126 *queue 队⾸结点出队列127*/128void queue_delete(queue *ac_queue)129 {130131if(queue_is_empty(ac_queue))132 {133 #ifdef AC_DEBUG134 printf("the queue is empty we can not delete head\n\n");135#endif136return;137 }138139 queue_node *head = ac_queue->head->next; //队⾸不存值,从队⾸的下⼀个结点开始出队列140141 ac_queue->head->next = head->next;142143if(head == ac_queue->tail)144 {//出队列为最后⼀个元素时将队列置空145 ac_queue->tail = ac_queue->head;146 }147148free(head); //释放队⾸结点内存149150 #ifdef AC_DEBUG151 queue_node_num--;152 printf("after delete the queue node num is %d :\n",queue_node_num);153#endif154 }155156/*157 *queue 释放queue内存158*/159void queue_destroy(queue *ac_queue)161 queue_node *p = NULL;162 p = ac_queue->head;163164while(p != NULL)165 {166167 #ifdef FREE_QUEUE_VALUE168if(p->value != NULL)169free(p->value); //value为动态申请内存的情况下做此操作170#endif171 queue_node *tmp = p->next;172173if(p != NULL)174free(p);175176 p = tmp;177 }178 }179180//ac状态节点181struct ac_node182 {183int final; //是否为⼀个模式串结尾的表⽰184int model; //标识该模式串为哪个模式串(如果考虑后缀⼦模式,此处应该改为整型链表) 185 ac_node *fail; //该状态节点的失效指针186187struct ac_node *next[CHAR_EXTERN];188 };189190/*191 * 创建状态节点192*/193 ac_node *ac_node_build()194 {195int i;196 ac_node *node = (ac_node *)malloc(sizeof(ac_node));197198if(node == NULL)199 {200 #ifdef AC_DEBUG201 printf("bulid node error the memory is full !! \n\n");202#endif203return NULL;204 }205206 node->final = 0;207 node->model = -1;208 node->fail = NULL;209210for(i = 0; i < CHAR_EXTERN; i++)211 {212 node->next[i] = NULL;213 }214215return node;216 }217218219/*220 * 创建trie树221 * return -1 失败 else 成功222*/223int ac_trie_build(ac_node *root,char *str,int len,int model)224 {225int i;226 ac_node *tmp = root;227228if(tmp == NULL)229 {230 #ifdef AC_DEBUG231 printf("root has not been init \n\n");232#endif233return -1;234 }235236for(i = 0; i < len; i++)237 {238239/*240 ac_node *next_node = tmp->next[str[i] - 'a'];241这样写然后对next_node操作会造成trie树建⽴失败,由于next_node⼀直不为NULL 242*/243244int index = str[i] - 'a'; // if CHAR_EXTERN=256 index = str[i]&0xff245if(tmp->next[index] == NULL)246 {247 tmp->next[index] = ac_node_build();248249if(tmp->next[index] == NULL)250 {251 #ifdef AC_DEBUG252 printf("build node error in ac_trie_build !!\n");253#endif254return -1;255 }256257 }258259 tmp = tmp->next[index];260 }261262 tmp->final = 1;263 tmp->model = model;264265return0;266 }267268269/*270* 创建失效指针函数271*/272273void ac_build_fail(ac_node *root,queue *ac_queue)274 {275if(root == NULL || ac_queue == NULL)276 {277 #ifdef AC_DEBUG278 printf("build ac fail pointer error -- input\n");279#endif280return ;281 }282283int i;284 queue_node *q_node = NULL;285 ac_node *tmp_node = NULL;286 ac_node *fail_node = NULL;287288 q_node = queue_build_node(root);289 queue_insert(ac_queue,q_node);290291while(!queue_is_empty(ac_queue))292 {293 tmp_node = queue_first(ac_queue);294 #ifdef AC_DEBUG295 printf("out the queue the ac node pointer is %p \n",tmp_node);296#endif297 queue_delete(ac_queue);//队⾸元素出队列298299for(i = 0; i < CHAR_EXTERN; i++)300 {//通过队列采⽤BFS(⼴度优先)的遍历顺序来计算当前状态每个字符的失效函数301302if(tmp_node->next[i] != NULL) // if CHART_EXTERN=255 tmpnode->next[i&0xff] 303 {304if(tmp_node == root)305 {306 tmp_node->next[i]->fail = root; //第⼀层节点的失效指针指向根结点307 }308else309 {310 fail_node = tmp_node->fail; //⽗结点的失效指针311312while(fail_node != NULL)313 {//当直到回到根结点时314if(fail_node->next[i] != NULL)315 {//在⽗结点的失效指针中找到当前字符的外向边316 tmp_node->next[i]->fail = fail_node->next[i];317break;318 }319320 fail_node = fail_node->fail; //继续递归321 }322323if(fail_node == NULL)324 {//找不到失效指针，则失效指针为根结点325 tmp_node->next[i]->fail = root;326 }327328 }329330 q_node = queue_build_node(tmp_node->next[i]);331 queue_insert(ac_queue,q_node); //将当前层的结点插⼊队列继续进⾏⼴度优先遍历332 #ifdef AC_DEBUG333 printf("insert into a ac node into queue the state is : %c \n\n", i + 'a');334 printf("insert the ac node pointer is %p\n",tmp_node->next[i]);335#endif336 }337 }338 }339 }340341/*342 *模式匹配函数343 *return -1 未匹配到任何模式 else 匹配到的当前的模式串的值344*/345int ac_query(ac_node *root,char *str,int len)346 {347if(root == NULL || str == NULL)348 {349return -1;350 }351352int i,match_num = 0;353int index = 0;354355 ac_node *tmp_node = NULL;356 ac_node *p = root;357358for(i = 0; i < len; i++)359 {360 index = str[i] - 'a'; // if CHAR_EXTERN=256 index = str[i]&0xff361362while(p->next[index] == NULL && p != root)363 {//状态在当前字符不进⾏转移以后的失效转移364 p = p->fail;365 }366367 p = p->next[index]; //将状态进⾏下移368369if(p == NULL)370 {//未找到失效指针,从根结点开始继续371 p = root;372 }373374 tmp_node = p; //计算当前状态下的匹配情况(在局部定义指针型变量经常出现内存指向问题) 375376while(tmp_node != root)377 {378if(tmp_node->final == 1)379 {380 match_num++;381382//tmp_node = tmp_node->fail; //匹配⼦模式串383384return tmp_node->model; //此处不进⾏return 可以计算多个模式串385 }386387 tmp_node = tmp_node->fail; //匹配⼦模式串388 }389390 }391392return -1;393 }394395/*396 *打印trie树397*/398void ac_trie_print(ac_node *root)399 {//利⽤队列进⾏⼴度优先遍历并打印trie树400 ac_node *ac_queue[256];401int i,head,tail;402 head = tail = 0;403404 memset(ac_queue,0,sizeof(ac_queue));405406 ac_node *tmp = root;407408 ac_queue[tail++] = tmp;409while(head != tail)410 {411 tmp = ac_queue[head++]; //出队列412for(i = 0; i < CHAR_EXTERN; i++)413 {414if(tmp->next[i] != NULL)415 {416 printf("%c ",i+'a');417 ac_queue[tail++] = tmp->next[i]; //将当前层的所有节点⼊队列418 }419 }420421 printf("\n");422423 }424 }425426427#define LIB_MODEL_NUM 10428429int main()430 {431#if 1432char *lib_model_str[10] = {"wwwgooglecom",\433"wwwbaiducom",\434"www",\435"googlecom",\436"guoxin",\437"she",\438"her",\439"shr",\440"yes",\441"say"};442443#endif444445#if 0446447char *lib_model_str[LIB_MODEL_NUM] = {448"she",\449"he",\450"say",\451"shr",\452"her"\453 };454#endif455456int i;457char str[1024];458 queue *ac_queue = NULL;459 ac_node *root = NULL;460461 ac_queue = queue_init();462 root = ac_node_build();463464for(i = 0; i < LIB_MODEL_NUM; i++)465 {466 ac_trie_build(root,lib_model_str[i],strlen(lib_model_str[i]),i);467 }468469470 ac_trie_print(root);471472 ac_build_fail(root,ac_queue);473474while(1)475 {476 printf("input the match string:\n\n");477478 scanf("%s",str);479480if(strcmp(str,"quit") == 0)481 {482return -1;483 }484485int model = ac_query(root,str,strlen(str));486487if(model == -1)488 {489 printf("not match!!\n\n");490 }491else492 {493 printf("match the model '%d' and the model string is %s \n\n",model,lib_model_str[model]); 494 }495 }496497return0; 498 }。
Aho-Corasickautomaton（AC自动机）解析及其在算法竞赛中的典型应用举例
Aho-Corasickautomaton（AC⾃动机）解析及其在算法竞赛中的典型应⽤举例摘要： 本⽂主要讲述了AC⾃动机的基本思想和实现原理，如何构造AC⾃动机，着重讲解AC⾃动机在算法竞赛中的⼀些典型应⽤。
什么是AC⾃动机？如何构造⼀个AC⾃动机？AC⾃动机在算法竞赛中的典型应⽤有哪些？例题解析什么是AC⾃动机？ 什么是AC⾃动机，不是⾃动AC的机器（想的美），⽽是⼀种多模匹配算法，英⽂名称Aho-Corasick automaton（前⾯的⼀串据说是⼀位科学家的名字），于1975年诞⽣于贝尔实验室。
回忆之前的KMP算法解决的⼀类问题是给出⼀个模板和⼀个⽂本串，问这⼀个模板在该⽂本串中的存在情况（包括是否存在、存在⼏次、哪些位置等等）。
现在如果是多个模板呢？可能你会想到⼀个⼀个拿出来⽤KMP算法进⾏匹配，但是如果⽂本串很长，模板⼜很多的话，KMP算法就不适合了(不满⾜于能解决问题，⽽追求⼜快⼜好的解决问题是算法研究的源动⼒)。
⽽AC⾃动机正是为了解决这类问题⽽⽣的。
基本思想 不得不重提的是KMP算法之所以能够在⾼效的处理单模匹配问题，主要得益于next数组的建⽴，能够使匹配的状态在线性的字符串上进⾏转移，使得失配后副串能够尽可能的“滑的远⼀些“。
⽽AC⾃动机也有类似功能的⼯具那就是fail指针。
应该能想到的是单模匹配的KMP算法的状态转移图是线性的字符串加上失配边组成的，那么多模匹配的AC⾃动机算法的状态转移图是字典树加上失配边组成的。
为了说明实际问题，直接看⼀个例⼦如下： 问题很明确，我们需要只遍历⼀遍⽂本串就找出所有单词表中存在的单词（只遍历⼀遍的想法和KMP算法有异曲同⼯之妙）。
我们先根据字符集合{she,he,say,shr,her}建⽴字典树如上图所⽰，然后我们拿着yasherhs去匹配，发现前两个字符⽆法匹配，跳过，第三个字符开始，she可以匹配，记录下来，继续往后⾛发现没有匹配了，结果就是该⽂本串只存在⼀个单词，很明显，答案是错的，因为存在she、he、her三个单词。
AC自动机基础入门
在树中插入单词
在这里的操作对于不同的题目 一般有3种不同的操作。 1：s[ind].count++; 这个是在解决出现总次数的时 候是这样处理的。 2：s[ind],count=1; 这个是在ac自动机上进行dp的 时候经常用的。 3.新加一个标记id。 这个是在处理有哪些单词出现 过。
void make_fail() { qin = qout = 0; int i, ind, ind_f; for(i = 0; i < 26; i++) { if(s[0].next[i] != -1) { q[qin++] = s[0].next[i]; } } while(qin != qout) { ind = q[qout++]; for(i = 0; i < 26; i++) { //找之后的子节点 if(s[ind].next[i] != -1) { q[qin++] = s[ind].next[i]; ind_f = s[ind].fail; while(ind_f > 0 && s[ind_f].next[i] == -1) ind_f = s[ind_f].fail; if(s[ind_f].next[i] != -1) ind_f = s[ind_f].next[i]; s[s[ind].next[i]].fail = ind_f;//子节点的fail根据父节点fail指针的搞定 } } }
AC自动机
by 李翔
AC自动机
• 不是accept自动机。
• 是Aho-Corasick 造出来的。所以你懂的
用途
• 字符串的匹配问题 • 多串的匹配问题 • 例如给几个单词 acbs，asf,dsef, • 再给出一个 很长的文章，acbsdfgeasf • 问在这个文章中，总共出现了多少个单词， 或者是单词出现的总次数。
AC自动机
关键字:AC自动机自动机有限状态自动机 Trie 字母树字符串匹配多串匹配算法Note:阅读本文需要有KMP算法基础，如果你不知道什么是KMP，请看这里：/blog/article.asp?id=146(Matrix67大牛写的) AC自动机是用来处理多串匹配问题的，即给你很多串，再给你一篇文章，让你在文章中找这些串是否出现过，在哪出现。
也许你考虑过AC自动机名字的含义，我也有过同样的想法。
你现在已经知道KMP了，他之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。
那么AC自动机也是同样的，他是Aho-Corasick。
所以不要再YY 地认为AC自动机是AC(cept)自动机，虽然他确实能帮你AC一点题目。
扯远了。
要学会AC自动机，我们必须知道什么是Trie，即字母树。
如果你会了，请跳过这一段Trie是由字母组成的。
先看张图：这就是一棵Trie树。
用绿色标出的点表示一个单词的末尾（为什么这样表示？看下去就知道了）。
树上一条从root到绿色节点的路径上的字母，组成了一个“单词”。
/* 也许你看了这一段，就知道如何构建Trie了，那请跳过以下几段。
*/那么如何来构建一棵Trie呢？就让我从一棵空树开始，一步步来构建他。
一开始，我们有一个root：现在，插入第一个单词，she。
这就相当于在树中插入一条链。
过程很简单。
插完以后，我们在最后一个字母’e’上加一个绿色标记，结果如图：再来一个单词，shr(什么词？…..右位移啊)。
由于root下已经有’s’了，我们就不重复插入了，同理，由于’s’下有’h’了，我们也略过他，直接在’h’下插入’r’，并把’r’标为绿色。
结果如图：按同样的方法，我们继续把余下的元素插进树中。
最后结果:也就是这样:好了，现在我们已经有一棵Trie了，但这还不够，我们还要在Trie上引入一个很强大的东西：失败指针或者说shift数组或者说Next函数…..你爱怎么叫怎么叫吧，反正就是KMP的精华所在，这也是我为什么叫你看KMP的原因。