首页 > 其他分享 >AC自动机

AC自动机

时间:2024-08-18 17:05:12浏览次数:11  
标签:AC trie ++ int fail 自动机 节点

AC 自动机

前言

我觉得AC自动机这种东西非常抽象,有必要写一篇博客来整理一下,以加深理解。

概况

AC自动机是以 Trie 树的结构为基础,结合 KMP 思想建立的自动机,用于解决多模式串匹配等任务。

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

  1. 把所有的模式串建成一颗 Trie 树。
  2. 用 KMP 的思想对 Trie 树上所有的节点构建失配指针。

字典树构建

字典树即 Trie 树,它的构建不必多说。拿 ABC、BCD、BD、C 这四个字符串举个例子,构建出来的 Trie 树就是这个样子(如图1),为了方便,我们把每个节点所代表的字符作为它的入度的边的边权。

图1
void insert(char s[]) {
	int u = 1, len = strlen(s);
	for (int i = 0; i < len; i++) {
		int v = s[i] - 'a';
		if (!trie[u][v]) trie[u][v] = ++tot;
		u = trie[u][v];
	}
	cnt[u]++; // 具体看情况
}

失配指针

含义

失配指针即 fail 指针,我们记 $u$ 的 fail 指针为 $fail[u]$。对于 $u$ 节点所对应的字符串而言,AC 自动机上的所有字符串当中,$fail[u]$ 为该字符串的最长后缀。举个例子,图1中,节点 4 对应的字符串为 ABC,它在 AC 自动机上能找到的最长后缀是 BC,所以节点 4 的 fail 指针指向 6。

构建

首先我们显然可以知道,一个节点的 fail 指针指向的点的深度一定是比该点要小的。所以 $fail[1]$ 就是 $root$(也就是 $0$)。

设点 $u$ 下的字符 $i$ 所对应的节点为 $trie[u][i]$。

  1. 若存在节点 $trie[u][i]$,则 $fail[trie[u][i]]=trie[fail[u]][i]$。还是拿图1举例子,现在以求出 $fail[3]=5$,那么 $fail[trie[3][C]]=trie[fail[3]][C]$ 即 $fail[4]=6$。
  2. 若不存在节点 $trie[u][i]$(即 $trie[u][i]=0$),则 $trie[u][i]=trie[fail[u]][i]$ 。依旧是拿图1举例子,显然节点 $trie[3][D]$ 不存在,而 $fail[3]$ 和 $3$ 所代表的字符串(后缀)是相同的,所以我们从 $3$ 向 $trie[fail[3]][D]$ 连一条边,即从 $3$ 向 $7$ 连一条边,这样节点 $trie[3][D]$ 就存在了。
  3. 因为要求出父亲节点的 fail 再求儿子的 fail,所以我们用广搜来实现。

然后我们的 trie 树(图)就会变成这个样子,如图2。虽然很抽象,但凑合着还能看。

图2
void getfail() {
	for (int i = 0; i < 26; i++) trie[0][i] = 1;	// 初始化0的所有儿子都是1
	q.push(1);										// 将根压入队列
	fail[1] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {				// 遍历所有儿子
			if (!trie[u][i]) {						// 如果不存在该节点,对应 2
				trie[u][i] = trie[fail[u]][i];		// 从u向trie[fail[u]][i]连一条边
				continue;
			}
			fail[trie[u][i]] = trie[fail[u]][i];	// 求fail,对应 1
			q.push(trie[u][i]);						// 将实点压入队列
		}
	}
}

怎么用

这还用说吗?看着用呗。

代码

拿例题来说事儿吧。[HDU 2222]Keywords Search

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = 1e6 + 10;
int n, t;
char s[M];
int trie[M][26], cnt[M], flag[M], fail[M];
int tot;
queue<int> q;
void insert(char s[]) { // 构建trie树
	int u = 1, len = strlen(s);
	for (int i = 0; i < len; i++) {
		int v = s[i] - 'a';
		if (!trie[u][v]) trie[u][v] = ++tot;
		u = trie[u][v];
	}
	cnt[u]++;
}
void getfail() {
	for (int i = 0; i < 26; i++) trie[0][i] = 1;	// 初始化0的所有儿子都是1
	q.push(1);										// 将根压入队列
	fail[1] = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; i++) {				// 遍历所有儿子
			if (!trie[u][i]) {						// 如果不存在该节点,对应 2
				trie[u][i] = trie[fail[u]][i];		// 从u向trie[fail[u]][i]连一条边
				continue;
			}
			fail[trie[u][i]] = trie[fail[u]][i];	// 求fail,对应 1
			q.push(trie[u][i]);						// 将实点压入队列
		}
	}
}
int query(char s[]) {
	int u = 1, len = strlen(s), ans = 0;
	for (int i = 0; i < len; i++) {
		int v = s[i] - 'a';
		int k = trie[u][v];
		while (k > 1 && flag[k] != -1) {
			ans = ans + cnt[k];
			flag[k] = -1;
			k = fail[k]; // 如果当前节点可以匹配成功的话,那么它的fail一定也可以
		}
		u = trie[u][v];
	}
	return ans;
}
void solve() {
	memset(trie, 0, sizeof(trie));
	memset(flag, 0, sizeof(flag));
	memset(fail, 0, sizeof(fail));
	memset(cnt, 0, sizeof(cnt));
	tot = 1; 			// 这十分重要
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s); // 读入模式串
		insert(s); 		// 把模式串扔到trie树里
	}
	getfail();
	scanf("%s", s);		// 读入文本串
	printf("%d\n", query(s)); // 拿文本串查询
}
int main() {
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

AC 自动机上 DP

懵了吧?因为 AC 自动机本质上是 trie 树,是一棵,所以他自然是可以 dp 的。既然它是一棵树,那就可以进行更多的树上操作,比如树剖。

AC 自动机上 dp 一般比较套路。$dp_{i,j}$ 表示当前在 $i$ 节点,且串长为 $j$ 的情况。有时候再加一维表示选了些什么(状压)。

然后就没了。

标签:AC,trie,++,int,fail,自动机,节点
From: https://www.cnblogs.com/zsk123qwq/p/18365806

相关文章

  • Class com.sun.tools.javac.tree.JCTree$JCImport does not have member field 'com.s
    环境:JDK21问题原因是Lombok,与JDK21兼容的最低Lombok版本是1.18.30,最小的SpringBoot版本是3.1.4。解决:将lombook版本改为1.18.30<dependencies><dependency><groupId>org.projectlombok</groupId><artifactId>lomb......
  • FusionCharts Suite XT 4.0 Crack
    FusionChartsSuiteXTproductgallerypageFusionChartshelpsyoubuildbeautifuldashboardsforyourweb&mobileprojects.Withextensivedocumentation,cross-browsersupport,andaconsistentAPI,itiseasierthanevertoaddinteractiveandrespo......
  • 专业图像处理与编辑软件Adobe Photoshop PS2024 win/mac软件安装下载
    一、软件概述1.1Photoshop简介AdobePhotoshop,简称PS,是全球领先的专业图像处理与编辑软件,由AdobeSystems开发和发行。自1990年问世以来,Photoshop凭借其强大的图像编辑、修复、合成及色彩管理能力,成为了图形设计师、摄影师、艺术家及数字内容创作者不可或缺的工具。1.2应......
  • Aspose.Total for .NET 24.5 Crack
    FileFormatSDKs:::Morethan80%ofFortune100companiestrustAsposeSDKstoCreate,Edit,ExportandConvertover100fileformatsintheirapplications. Aspose.Total:::::ProductFamilyAspose.WordsProductSolutionAspose.PDFProductSolutionAspos......
  • 【888题竞赛篇】第三题,2016ICPC大连-Detachment
    这里写自定义目录标题更多精彩内容256题算法特训课,帮你斩获大厂60W年薪offer原题2016ICPC大连-DetachmentB站动画详解问题分析思路分析1.预处理前缀和与前缀积2.二分查找分割点3.分配剩余长度4.证明最佳分配策略5.模运算与逆元算法实现1.预处理前缀和、前缀积及......
  • AlphaFold2:Highly accurate protein structure prediction with AlphaFold(蛋白质结构
    ICLR-15July2021MainMethod:MSA+EvoformerPytorchcode:https://github.com/lucidrains/alphafold2literatures:https://www.nature.com/articles/s41586-021-03819-2JohnJumper,RichardEvans,AlexanderPritzel,TimGreen,MichaelFigurnov,OlafRonneberger......
  • P1466 [USACO2.2] 集合 Subset Sums
    题目描述对于从\(1\simn\)的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的。举个例子,如果\(n=3\),对于\(\{1,2,3\}\)能划分成两个子集合,每个子集合的所有数字和是相等的:\(\{3\}\)和\(\{1,2\}\)是唯一一种分法(交换集合位置被认为是同一种划分方案,因此不......
  • k8s 安装nacos集群
    需求使用k8s部署nacos集群,nacos的数据主要保存在mysql中,因此nacos运行时不需要考虑持久化问题。这里使用2.3.2版本 导入mysql数据github地址:https://github.com/alibaba/nacos/releases找到2.3.2版本,下载压缩包,得到nacos-server-2.3.2.tar.gz解压文件,找到文件nacos\conf\m......
  • AvaloniaChat—从源码构建指南
    AvaloniaChat介绍一个使用大型语言模型进行翻译的简单应用。我自己的主要使用场景在看英文文献的过程中,比较喜欢对照着翻译看,因此希望一边是英文一边是中文,虽然某些软件已经自带了翻译功能,但还是喜欢大语言模型的翻译,但每次都要将英文复制粘贴过去还要自己手动添加prompt,还无法......
  • 高性能内存对象缓存Memcached原理与部署
    案例概述Memcached概述一套开源的高性能分布式内存对象缓存系统所有的数据都存储在内存中支持任意存储类型的数据提高网站的访问速度数据存储方式与数据过期方式数据存储方式:SlabAllocation按组分配内存,每次分配一个Slab,相当于一个大小为1M的页,然后再1M的空间里根......