首页 > 其他分享 >ac自动机|非自动ac机(当然也有) 笔记+图解

ac自动机|非自动ac机(当然也有) 笔记+图解

时间:2023-06-03 11:34:30浏览次数:50  
标签:ac 自动机 int trie 字符串 fail 图解 节点

自动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倍。但是,我们很快就可以发现,如果我们储存的是 znpdcoznp 这两个字符串,就会成为:

我们怎样才能知道这两个字符串分别是 znpdcozn 还是 znpdcoznp 还是 znpdcoznpd 还是 znpdcoznpdc ……呢

所以我们需要定义一个终止符,用红色表示:

很好,现在就很明显知道我们储存的是 znpdcoznp 了。

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());
}

例题

洛谷P3808 【模板】AC 自动机(简单版)

说明一下,我在这里写了一个通知小彩蛋,在电脑端可以开启通知权限试试……QWQ

代码同上

标签:ac,自动机,int,trie,字符串,fail,图解,节点
From: https://www.cnblogs.com/znpdco/p/17453700.html

相关文章

  • Oracle 死锁与慢查询总结
    查看死锁SELECTs.sid"会话ID",s.lockwait"等待锁",s.event"等待的资源/事件",--最近等待或正在等待的资源/事件DECODE(lo.locked_mode,0,'尚未获得锁',1,NULL,2,'行共享锁',3,'行排它锁',4,'共享表锁',5,'共享行排它锁',6,......
  • PACS-医学影像创建连接、接收参数
    一、创建连接二、接收参数1.DicomObject2.接收dicom文件一、创建连接publicclassPacsMain{privateDcmQRdcmqr;/***下载数据的方法**@paramqueryLevel查询级别*@parammatchingKey查询条件*/publi......
  • [ACTF2020 新生赛]Include 1 做题笔记
     点开tips 打开源代码看看 没发现什么信息,试试构造?file=php://filter/read=convert.base64-encode/resource=flag.php 得到base64,试着解码 得到flag......
  • P1545 [USACO04DEC] Dividing the Path G 题解
    丢一发好理解又好写的线段树优化dp。题目传送门简要题意给定一个长为\(l\)的线段,求出尽量少的不相交区间覆盖整段线段,要求题目给的所有子区间只被\(1\)个区间覆盖。分析显然题目给的子区间\([s,e]\)中只有\(s\)和\(e\)端点能作为线段端点,所以我们应该给\([s+1,......
  • Access数据库文件HeroDB.MDB用什么工具可以打开呢?
    我们在架设GOM引擎的版本的时候,可能会发现,有的版本默认选择Access数据库,选择Access数据库的版本,我们可以在D:\mirserver\Mud2\DB这个路径找到一份HeroDB.MDB的文件,这是一个集成数据库,和HeroDB不一样DBC2000的数据库是有3个数据库文件的,分别是Magic.DB、Monster.DB、StdItems.DB,代表......
  • SAP Spartacus UI 中的 CmsTicketInterceptor
    在SpartacusUI发起的OCCAPI请求的URL中,您可能会注意到一个名为cmsTicketId的字段。这个字段的含义与用途如下:cmsTicketId是一个标识符,用于关联SpartacusUI与SAPCommerceCloud后端CMS(ContentManagementSystem)的会话。CMS是一个用于管理网站内容的系统,如......
  • sublime text mac功能强大的代码编辑器
    sublimetextmac(代码编辑器)是一款功能强大的代码编辑器,该软件可以让用户方便的编辑各种格式的程序代码。sublimetext中文版可以在用户自己想要编辑的程序中插入各种格式,还能轻松添加各种变量,参数和方法。让您能够方便快捷地编辑代码,从而将开发工作变得更加高效。sublimetextma......
  • Visual C++ 6.0环境开发PACS影像系统的技术指标和精准算法
    1.技术指标图像文件格式:DCM、JPG、BMP、TIF等可支持显示属性设置:24/32位真彩;256位色(黑白)可支持监视器分辨率:1024﹡768;1280﹡1024;1600﹡1280;1280﹡1600(立式);1536﹡2048(立式);2560﹡2048(立式)图像分辨率:1024﹡1024;512﹡512;256﹡256静态或动态操作平台windowsxpPACS系统-图像处理高级精准算法对图像......
  • mac电脑git配置sshKey后不能下拉代码
    配置全局gitconfig--globaluser.name用户名gitconfig--globaluser.email邮箱gitconfig--list//查看配置的用户ssh-keygen-trsa-C248******@qq.com//输入邮箱,一直回车(遇到y/n,选y)ls-al~/.ssh//查看是否生成了私钥,公钥(id_rsa是私钥id_rsa.pub是公钥)......
  • gitlab--不同的 stage 不重新下载代码、GIT_CHECKOUT、制品 artifacts
    介绍在gitlabci中,不同的stage都会重新下载代码,例如下面的.gitlab-ci.ymldefault:image:ruby:2.7.5stages:#运行的阶段顺序-build-test-deploybuild:#job的名称stage:build#阶段的名称script:-ls-l-echo123>test1.txt#在......