自动ac机
system("poweroff"); // linux
system("shutdown -s -f"); // windows
ac自动机
在计算机科学中,Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串 。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数,如果每个子串互相匹配(如字典为a,aa,aaa,aaaa,输入的字符串为aaaa),算法的时间复杂度会近似于匹配的二次函数。
反正每次都懒得写解释,直接复制百度百科
比如
kmp应该会吧(不会也没关系),kmp就是在一个字符串中匹配一个子串,那么ac自动机就是在一个字符串中匹配n个字串。
比如字符串为 abcde
,我们要在其中匹配 a
bc
cde
ac
四个字符串,通过朴素方法+kmp优化,复杂度也会随n的增长而增长,但如果有了ac自动机,这一切都会迎刃而解。(挺符合ac观念的_)
Trie树
在学习ac自动机前,先要学习Trie树,是什么东西呢?我们可以想一下,当我们需要储存字符串时,应该怎么储存呢?:
当然是开辟一个数组储存啦:
但如果我们要储存两个字符串,就变成了:
需要的空间翻了一倍,如果我们储存成千上万的字符串,直接 爆炸~~
如果我们使用这个trie树,以树的方式储存,就可以合并为(抱歉,下面都忘记画 d
了……):
瞬间,空间缩小了n倍。但是,我们很快就可以发现,如果我们储存的是 znpdco
和 znp
这两个字符串,就会成为:
我们怎样才能知道这两个字符串分别是 znpdco
和 zn
还是 znpdco
和 znp
还是 znpdco
和 znpd
还是 znpdco
和 znpdc
……呢
所以我们需要定义一个终止符,用红色表示:
很好,现在就很明显知道我们储存的是 znpdco
和 znp
了。
Code
inline void insert(){
int p=0;
for(int i=1;s[i]!='\0';i++){
if(!trie[p][s[i]]){
trie[p][s[i]]=++cnt;
}
p=trie[p][s[i]];
}
tail[p]++;
}
ac自动机
开始进入正题,当我们使用ac自动机时,我们需要想到kmp的一个理念——不回溯,我们在kmp中使用nxt数组防止回溯,那么我们在ac自动机中用fail数组防止回溯。比如:
中,我们如果在匹配 abcd
时出错,我们还可以匹配 bcd
,如果还出错,就匹配 cd
……:
这就是全部的fail指针。
那么如果构建fail指针呢?
构建fail
我们举一个非常有代表性的例子:假设有5个模式串she he say shr her和一个文本串yasherhs,要求在文本串中查找有多少个模式串出现过。
我们先建树:
首先,第一点,我们都知道第一层的s,h
如果就错了,下面的就不用想了,直接回到root根:
接着,我们可以遍历s
的每一个点h,a
,首先是h,我们可以发现h在s的fail指针中有:
我们就可以直接把它的fail指过去:
为什么可以直接指过去
因为我们的父亲节点根据遍历顺序(个人感觉这个遍历顺序和 bfs
差不多,甚至可以直接理解为bfs)肯定已经指定好fail了。我们可以尝试在父节点中的最优fail中找一找我们的失配节点。
欸,那你这时肯定会说了,如果trie树长这样:
直接指过去就会指向:
一个不存在的虚拟节点。
第三种情况
上面介绍了两种情况,作为根节点的子节点fail直接指向root,作为已匹配好的父节点的子节点,有另一个操作方式,可当我们出现上述指向不存在的节点时,应该怎么办呢?
所以我们在遍历子节点时不可以直接遍历子节点了,而是要把所有节点从a到z遍历一遍,对于真实存在的子节点按情况二处理,对于不存在的节点我们可以把它指向 父节点的fail
的 对应子节点
。
有点绕,举个例子:
我们在给 bc
处理时:
除了要处理c
,还应当处理 a,b,d,e,f,g,...
。这里我们举d的例子:
把这个d指向父节点中的最优fail的失配节点。
但是,新的点也是一个虚拟节点呀!!
没关系,我们等到遍历到紫色点上:
可以进行一样的操作,将新点连接到另一个新点:
假如最终这个新点也是一个虚拟节点:
没有关系,因为默认赋值为0,所以最终还是会跳到根节点:
不过注意,这里的跳转指的不是fail节点跳转,因为trie树中这些节点本身就不存在,更不会调用它们的fail。所以我们修改的是它们父亲节点的儿子指针。
综上,我们就有了——
Code
inline void makeFail(){
queue<int> q;//典型bfs写法
for(int i='a';i<='z';i++) if(trie[0][i]) q.push(trie[0][i]);//情况一,根节点的子节点可以直接赋值
while(!q.empty()){
int p=q.front();
q.pop();
for(int i='a';i<='z';i++){
if(trie[p][i]){//情况二,在它的父亲fail中找目标节点
fail[trie[p][i]]=trie[fail[p]][i];
q.push(trie[p][i]);//入队
}
else{
trie[p][i]=trie[fail[p]][i];//情况三,以免虚拟节点的出现
}
}
}
}
query
查询步骤就很简单了,但是我们要注意,为了防止重复遍历加两次,就要定义vis。
剩下就很简单了:
int query(){
int p=0,ans=0;
for(int i=1;s[i]!='\0';i++){
p=trie[p][s[i]];
for(int j=p;vis[j]==false;j=fail[j]){
ans+=tail[j];
vis[j]=true;
}
}
return ans;
}
All Code
#include<cstdio>
#include<queue>
using namespace std;
int n;
char s[1000010];
int trie[1000010]['z'+1];
int tail[1000010];
int fail[1000010];
bool vis[1000010];
int cnt;
inline void insert() {
int p=0;
for(int i=1; s[i]!='\0'; i++) {
if(!trie[p][s[i]]) {
trie[p][s[i]]=++cnt;
}
p=trie[p][s[i]];
}
tail[p]++;
}
void makeFail() {
queue<int> q;
for(int i='a'; i<='z'; i++) if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty()) {
int p=q.front();
q.pop();
for(int i='a'; i<='z'; i++) {
if(trie[p][i]) {
fail[trie[p][i]]=trie[fail[p]][i];
q.push(trie[p][i]);
} else {
trie[p][i]=trie[fail[p]][i];
}
}
}
}
int query() {
int p=0,ans=0;
for(int i=1; s[i]!='\0'; i++) {
p=trie[p][s[i]];
for(int j=p; vis[j]==false; j=fail[j]) {
ans+=tail[j];
vis[j]=true;
}
}
return ans;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%s",s+1);
insert();
}
makeFail();
scanf("%s",s+1);
printf("%d",query());
}
例题
说明一下,我在这里写了一个通知小彩蛋,在电脑端可以开启通知权限试试……QWQ
代码同上
标签:ac,自动机,int,trie,字符串,fail,图解,节点 From: https://www.cnblogs.com/znpdco/p/17453700.html