Dotcpp  >  编程教程  >  字符串相关  >  什么是AC自动机?

什么是AC自动机?

点击打开在线编译器,边学边练

AC自动机,我知道很多人看到这个会十分好奇,不过这个自动机它又叫做 Automaton。我相信大家在初学自动机相关内容时,许多人难以建立对自动机的初步印象,尤其是在自学的时侯。让我们切入正题,通过这段时间对自动机的研究,然后制作若干的gif,已经可以呈现出一个相对直观的自动机形态,我们先对基础的知识有个了解。


定义:AC自动机是以Trie的结构为基础,结合KMP的思想建立的


什么是AC自动机?

1. AC自动机是一种有限状态自动机(说了等于没说),它常被用于多模式串的字符串匹配。

2. 在学完AC自动机后,总结为: AC自动机是以Trie的结构为基础,结合KMP的思想建立的。 

注意:(AC = KMP + Trie) 但不完全是。


简单来说,建立一个 AC 自动机有两个步骤:

(1)基础的Trie结构:将所有的模式串构成一棵Trie树。

(2)KMP的思想:对Trie树上所有的结点构造失配指针,然后就可以利用它进行多模式匹配了。


关于Trie树构造

和trie树的插入操作一样,将模式串存入

void insert(char *s){
int u=1,len=strlen(s); //从1开始跳
for(register int i(0) ; i<len ; i=-~i){
int c=s[i]-'a';
if(!ch[u][c]) ch[u][c] = ++tot; //没有这个字母的边的话,新建一条
u = ch[u][c]; //接着往下跳
}
bo[u]++; //将这个点标记为一个单词的结尾
return;
}

这并不是关于AC自动机的详细内容,但是可以帮助大家先理性的认识,后期多练习。



本文固定URL:https://www.dotcpp.com/course/1015

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)