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