首页 > 其他分享 >「学习笔记」AC 自动机

「学习笔记」AC 自动机

时间：2023-07-21 21:11:06浏览次数：75  
标签：AC cur int tr ac 笔记 ++ fail 自动机

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

Trie 的构建

这里需要仔细解释一下 Trie 的结点的含义，Trie 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，Trie 的边就是状态的转移。

形式化地说，对于若干个模式串 \(s_1, s_2 \dots s_n\)，将它们构建一棵字典树后的所有状态的集合记作 Q。

失配指针

个人感觉这里是最难理解的。

AC 自动机利用一个 fail 指针来辅助多模式串的匹配。

状态 \(u\) 的 fail 指针指向另一个状态 \(v\)，其中 \(v \in Q\)，且 \(v\) 是 \(u\) 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。

只需要知道，AC 自动机的失配指针指向当前状态的最长后缀状态即可。

构建指针

构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。

考虑字典树中当前的结点 \(u\)，\(u\) 的父结点是 \(p\)，\(p\) 通过字符 \(c\) 的边指向 \(u\)，即 \(trie[p,\mathtt{c}]=u\)。假设深度小于 \(u\) 的所有结点的 fail 指针都已求得。

  1. 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 存在：则让 \(u\) 的 fail 指针指向 \(\text{trie}[\text{fail}[p],\mathtt{c}]\)。相当于在 \(p\) 和 \(\text{fail}[p]\) 后面加一个字符 \(c\)，分别对应 \(u\) 和 fail[u]。

  2. 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 不存在：那么我们继续找到 \(\text{trie}[\text{fail}[\text{fail}[p]],\mathtt{c}]\)。重复 \(1\) 的判断过程，一直跳 fail 指针直到根结点。

  3. 如果真的没有，就让 fail 指针指向根结点。
    如此即完成了 \(\text{fail}[u]\) 的构建。

如此即完成了 \(\text{fail}[u]\) 的构建。

实现

定义

struct node {
    int fail;
    int tr[26];
    int End;
} ac[N];

fail 是失配指针，tr 是字典树，End 是当前状态是否为一个字符串的结束。

插入

这里就是最基本的字典树插入操作。

void Insert(char* s) {
    int l = strlen(s), u = 0;
    for (int i = 0; i < l; ++ i) {
        if (ac[u].tr[s[i] - 'a'] == 0) {
            ac[u].tr[s[i] - 'a'] = ++ tot;
        }
        u = ac[u].tr[s[i] - 'a'];
    }
    ++ ac[u].End;
}

构建失败指针

我们用队列广搜的方式来构建失败指针，按照上面的步骤：

  • 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 存在：则让 \(u\) 的 fail 指针指向 \(\text{trie}[\text{fail}[p],\mathtt{c}]\)。相当于在 \(p\) 和 \(\text{fail}[p]\) 后面加一个字符 \(c\)，分别对应 \(u\) 和 fail[u]。

  • 如果 \(\text{trie}[\text{fail}[p],\mathtt{c}]\) 不存在：那么我们继续找到 \(\text{trie}[\text{fail}[\text{fail}[p]],\mathtt{c}]\)。重复 \(1\) 的判断过程，一直跳 fail 指针直到根结点。

  • 如果真的没有，就让 fail 指针指向根结点。
    如此即完成了 \(\text{fail}[u]\) 的构建。

void get_fail() {
	queue<int> q;
	for (int i = 0; i < 26; ++ i) {
		if (ac[0].tr[i] != 0) {
			ac[ac[0].tr[i]].fail = 0;
			q.emplace(ac[0].tr[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++ i) {
			if (ac[u].tr[i]) {
				ac[ac[u].tr[i]].fail = ac[ac[u].fail].tr[i];
				q.emplace(ac[u].tr[i]);
			} else {
				ac[u].tr[i] = ac[ac[u].fail].tr[i];
			}
		}
	}
}

查询

这里我们用模板题来说明。

查询有多少个模式串出现过

P3808 【模板】AC 自动机（简单版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

int ask(char* s) {
	int l = strlen(s);
	int u = 0, ans = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur && (~ac[cur].End); cur = ac[cur].fail) {
			ans += ac[cur].End;
			ac[cur].End = -1;
		}
	}
	return ans;
}

这里给 End 打上标记，是为了防止重复搜到这一个模式串，然后重复加入了答案。

完整代码：

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 1e6 + 5;

int n, tot;
char s[N];

struct node {
	int fail;
	int tr[26];
	int End;
} ac[N];

void Insert(char* s) {
	int l = strlen(s), u = 0;
	for (int i = 0; i < l; ++ i) {
		if (ac[u].tr[s[i] - 'a'] == 0) {
			ac[u].tr[s[i] - 'a'] = ++ tot;
		}
		u = ac[u].tr[s[i] - 'a'];
	}
	++ ac[u].End;
}

void get_fail() {
	queue<int> q;
	for (int i = 0; i < 26; ++ i) {
		if (ac[0].tr[i] != 0) {
			ac[ac[0].tr[i]].fail = 0;
			q.emplace(ac[0].tr[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++ i) {
			if (ac[u].tr[i]) {
				ac[ac[u].tr[i]].fail = ac[ac[u].fail].tr[i];
				q.emplace(ac[u].tr[i]);
			} else {
				ac[u].tr[i] = ac[ac[u].fail].tr[i];
			}
		}
	}
}

int ask(char* s) {
	int l = strlen(s);
	int u = 0, ans = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur && (~ac[cur].End); cur = ac[cur].fail) {
			ans += ac[cur].End;
			ac[cur].End = -1;
		}
	}
	return ans;
}

int main() {
	n = read<int>();
	for (int i = 1; i <= n; ++ i) {
		scanf("%s", s + 1);
		Insert(s + 1);
	}
	ac[0].fail = 0;
	get_fail();
	scanf("%s", s + 1);
	cout << ask(s + 1) << '\n';
	return 0;
}

查询出现次数最多的模式串

P3796 【模板】AC 自动机（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这里 End 存储的不再是简单的 \(1\) 了，而是当前这个状态对应的模式串的编号，目的是最后输出字符串。

void Insert(string s, int num) {
	int u = 0, l = s.size();
	for (int i = 0; i < l; ++ i) {
		if (!ac[u].tr[s[i] - 'a']) {
			ac[u].tr[s[i] - 'a'] = ++ cnt;
			clr(cnt);
		}
		u = ac[u].tr[s[i] - 'a'];
	}
	ac[u].End = num;
}

for (int i = 1; i <= n; ++ i) {
	cin >> st[i];
	Insert(st[i], i);
	Ans[i].first = 0;
	Ans[i].second = i;
}

除了查询和主函数，其他代码都是一样的。

查询代码：

void ask(char* s) {
	int l = strlen(s);
	int u = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur; cur = ac[cur].fail) {
			++ Ans[ac[cur].End].first;
		}
	}
}

这里的 Ans 是定义的答案数组，first 是记录出现的次数，second 是该状态的编号。

完整代码：

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 1e6 + 5;

int n, cnt;
char s[N];
string st[200];

struct node {
	int fail, End;
	int tr[26];
} ac[N];

pair<int, int> Ans[N];

void clr(int u) {
	for (int i = 0; i < 26; ++ i) {
		ac[u].tr[i] = 0;
	}
	ac[u].fail = ac[u].End = 0;
}

void Insert(string s, int num) {
	int u = 0, l = s.size();
	for (int i = 0; i < l; ++ i) {
		if (!ac[u].tr[s[i] - 'a']) {
			ac[u].tr[s[i] - 'a'] = ++ cnt;
			clr(cnt);
		}
		u = ac[u].tr[s[i] - 'a'];
	}
	ac[u].End = num;
}

void get_fail() {
	queue<int> q;
	for (int i = 0; i < 26; ++ i) {
		if (ac[0].tr[i] != 0) {
			ac[ac[0].tr[i]].fail = 0;
			q.emplace(ac[0].tr[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++ i) {
			if (ac[u].tr[i]) {
				ac[ac[u].tr[i]].fail = ac[ac[u].fail].tr[i];
				q.emplace(ac[u].tr[i]);
			} else {
				ac[u].tr[i] = ac[ac[u].fail].tr[i];
			}
		}
	}
}

void ask(char* s) {
	int l = strlen(s);
	int u = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur; cur = ac[cur].fail) {
			++ Ans[ac[cur].End].first;
		}
	}
}

void work() {
	cnt = 0;
	clr(0);
	for (int i = 1; i <= n; ++ i) {
		cin >> st[i];
		Insert(st[i], i);
		Ans[i].first = 0;
		Ans[i].second = i;
	}
	get_fail();
	scanf("%s", s + 1);
	ask(s + 1);
	sort(Ans + 1, Ans + n + 1, [](pii x, pii y) {
		return x.first == y.first ? x.second < y.second : x.first > y.first;
	});
	int l = 1;
	printf("%d\n", Ans[1].first);
	while (Ans[l].first == Ans[1].first) {
		cout << st[Ans[l].second] << '\n';
		++ l;
	}
}

int main() {
	n = read<int>();
	while (n) {
		work();
		n = read<int>();
	}
	return 0;
}

优化

先拿这道题来引入。P5357 【模板】AC 自动机（二次加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

你会发现它与 P3796 【模板】AC 自动机（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 十分的相似，似乎只要将最后的找出现次数最大的模式串改为输出所有模式串的出现次数就行了 反正当时我是这样想的，然后略微修改代码后交上发现。

image

果然，二次加强版就是不一样……

重新读题，意外发现最后一句话：数据不保证任意两个模式串不相同。

？？？不保证，读错题了！（不要犯这样的低级错误），这里还是比较简单的，只需要判一下重就好了，直接上代码，相信看到这里的聪明的你一定可以看懂它！修改的主要位置加上注释了。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 2e5 + 5;
const int M = 2e6 + 5;

int n, tot;
int ans[N], mp[N];
string st[N];
char s[M];
queue<int> q;

struct node {
	int End, fail;
	int tr[26];
} ac[N];

void Insert(string s, int num) {
	int l = s.length(), u = 0;
	for (int i = 0; i < l; ++ i) {
		if (!ac[u].tr[s[i] - 'a']) {
			ac[u].tr[s[i] - 'a'] = ++ tot;
		}
		u = ac[u].tr[s[i] - 'a'];
	}
	if (!ac[u].End) {// 修改点 1
		ac[u].End = num;
	}
	mp[num] = ac[u].End;
}

void get_fail() {
	for (int i = 0; i < 26; ++ i) {
		if (ac[0].tr[i]) {
			ac[ac[0].tr[i]].fail = 0;
			q.emplace(ac[0].tr[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++ i) {
			if (ac[u].tr[i]) {
				ac[ac[u].tr[i]].fail = ac[ac[u].fail].tr[i];
				q.emplace(ac[u].tr[i]);
			} else {
				ac[u].tr[i] = ac[ac[u].fail].tr[i];
			}
		}
	}
}

void ask(char* s) {
	int l = strlen(s), u = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur; cur = ac[cur].fail) {
			++ ans[ac[cur].End];
		}
	}
}

int main() {
	n = read<int>();
	for (int i = 1; i <= n; ++ i) {
		cin >> st[i];
		Insert(st[i], i);
	}
	get_fail();
	scanf("%s", s + 1);
	ask(s + 1);
	for (int i = 1; i <= n; ++ i) {
		printf("%d\n", ans[mp[i]]); // 修改点 2
	}
	return 0;
}

再次提交，得到了这样的结果。

image

没办法，去 \(\texttt{OI-Wiki}\) 上看了看，发现原来有优化，优化的方式使用 拓扑排序！

不会拓扑排序的朋友先去学习一下拓扑排序吧。拓扑排序 - OI Wiki (oi-wiki.org)

我们为什么会 T 呢？

看这段代码

void ask(char* s) {
	int l = strlen(s), u = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		for (int cur = u; cur; cur = ac[cur].fail) {
			++ ans[ac[cur].End];
		}
	}
}

我们沿着 fail 指针一步一步地跳，对于下面的图。

image

我们假设：

先搜到 \(14\) 号节点，答案更新；然后搜到了 \(13\) 号节点，答案更新，再找到 \(14\) 号节点，答案更新；之后搜到了 \(11\) 号节点，顺着 fail 答案更新；再之后搜到了 \(8\) 号节点，顺着 fail 答案更新。

你会发现，效率慢的很！然后就被这道题卡了。

如何提高效率的，我们可以在 \(8、11、13、14\) 号节点上各打上标记，然后从 \(8\) 号开始，标记顺着 fail 传递过去，最后统计的答案为：\(8\) 号统计了 \(1\) 次，\(11\) 号统计了 \(2\) 次，\(13\) 号统计了 \(3\) 次，\(14\) 号统计了 \(4\) 次，这样统计的答案与一次又一次地更新是一样的，但是这种方法效率高了很多。

具体怎么实现呢，就用拓扑排序，把 fail 指针作为边，最后 fail 指针一定不会成环，所以可以跑拓扑排序，修改一下代码就可以了。

/*
  The code was written by yifan, and yifan is neutral!!!
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline T read() {
	T x = 0;
	bool fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

const int N = 2e5 + 5;
const int M = 2e6 + 5;

int n, tot;
int ans[N], mp[N], in[N];
string st[N];
char s[M];
queue<int> q;

struct node {
	int End, fail, tag;
	int tr[26];
} ac[N];

void Insert(string s, int num) {
	int l = s.length(), u = 0;
	for (int i = 0; i < l; ++ i) {
		if (!ac[u].tr[s[i] - 'a']) {
			ac[u].tr[s[i] - 'a'] = ++ tot;
		}
		u = ac[u].tr[s[i] - 'a'];
	}
	if (!ac[u].End) {
		ac[u].End = num;
	}
	mp[num] = ac[u].End;
}

void get_fail() {
	for (int i = 0; i < 26; ++ i) {
		if (ac[0].tr[i]) {
			ac[ac[0].tr[i]].fail = 0;
			q.emplace(ac[0].tr[i]);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < 26; ++ i) {
			if (ac[u].tr[i]) {
				ac[ac[u].tr[i]].fail = ac[ac[u].fail].tr[i];
				q.emplace(ac[u].tr[i]);
				++ in[ac[ac[u].fail].tr[i]];
			} else {
				ac[u].tr[i] = ac[ac[u].fail].tr[i];
			}
		}
	}
}

void ask(char* s) {
	int l = strlen(s), u = 0;
	for (int i = 0; i < l; ++ i) {
		u = ac[u].tr[s[i] - 'a'];
		++ ac[u].tag; // 修改部分 1
	}
}

void topsort() { // 修改部分 2
	for (int i = 1; i <= tot; ++ i) {
		if (!in[i]) {
			q.emplace(i);
		}
	}
	while (!q.empty()) {
		int fr = q.front();
		q.pop();
		ans[ac[fr].End] = ac[fr].tag;
		int u = ac[fr].fail;
		ac[u].tag += ac[fr].tag;
		if (! (-- in[u])) {
			q.emplace(u);
		}
	}
}

int main() {
	n = read<int>();
	for (int i = 1; i <= n; ++ i) {
		cin >> st[i];
		Insert(st[i], i);
	}
	get_fail();
	scanf("%s", s + 1);
	ask(s + 1);
	topsort();
	for (int i = 1; i <= n; ++ i) {
		printf("%d\n", ans[mp[i]]);
	}
	return 0;
}

然后，我们就得到了想要的 AC！

image

完结！

标签：AC,cur,int,tr,ac,笔记,++,fail,自动机
From： https://www.cnblogs.com/yifan0305/p/17572382.html

相关文章

  • 如何快速判断Oracle数据库是否运行缓慢
    查看过去一分钟数据库的响应时间SETLINESIZE200PAGESIZE50000COLBEGIN_TIMEFORMATA17COLEND_TIMEFORMATA17COLINST_IDFORMAT999COL"ResponseTime(msecs)"FORMAT999,999,999,999.99SELECTTO_CHAR(BEGIN_TIME,'DD-MON-YYYYHH24:MI')BEGIN......
  • 树上启发式合并学习笔记
    树上启发式合并\((dsu\on\tree)\)适用条件：可以在一个子树内统计的问题，并且不带修改。暴力复杂度一般为\(O(n^2)\)。例题：CF600ELomsatgelral解法考虑一个问题，给你一棵树，每个节点有一个颜色，如果一种颜色在以\(x\)为根的子树内出现次数最多，则称\(col_i\)占主要色。......
  • 【学习笔记】【数学】概率与期望
    前言如果不小心发表出去了那么大概率是我手滑点错了，没有更新完那就是我也在学，有问题请@我。另外有同学告诉我概率期望其实是动态规划？基础知识：互斥事件：事件\(A\)和\(B\)的交集为空，\(A\)与\(B\)就是互斥事件，也叫互不相容事件。也可叙述为：不可能同时发生的事件。如\(A......
  • oracle 碰到过的问题
    1、指定的SID在本机上已经存在。请指定一个不同的SID 2、安装过程：未初始化服务句柄   http://space.yoka.com/blog/3063028/5692836.html   E:\oracle\product\10.2.0\db_1\NETWORK\ADMIN   将sqlnet.ora文件中的SQLNET_AUTHENTICATION_SERVICES=(NTS)修改为SQLNET_A......
  • Mac环境下，在 VS Code下执行Run Code打印Operation not permitted
    步骤1。打开系统设置；步骤2。选择隐私与安全性；步骤3。选择完全磁盘访问权限；步骤4。添加VisualStudioCode,输入完管理员密码后重启VSCode。......
  • 7.20 图论笔记
    T1题目•在\(N\)个点\(P\)条边的加权无向图上求出一条从\(1\)号结点到\(N\)号结点的路径，使路径上第\(K+1\)大的边权尽量小。•\(0≤K<N≤1000\),\(1≤P≤2000\)。Solution•一道自己做出来的蓝。•二分第\(K+1\)大边权为\(mid\)，每次把边权......
  • Codeforces 794G - Replace All
    一个比较垃圾的做法，卡着时限过了这道题。首先大胆猜个结论：要么\(|s|=|t|\)，此时\(A,B\)任取，要么存在字符串\(c\)和整数\(x,y\)使得\(A=c^x,B=c^y\)，其中\(c^x\)表示\(x\)个\(c\)拼接得到的结果。证明的话感觉还挺复杂的，可能要border引理之类的东西，不过我是先写了个......
  • win10+python3.8+Anaconda3+cuda10.2+cudnn7.6+pytorch安装教程
    版本问题很重要，为了这个版本，真的吐血版！！！其他链接1.cuda10.2+cudnn7.6安装和测试的方法2.彻底卸载Anaconda3.新建的虚拟环境总是在c盘怎么解决1.安装Anaconda3在Anaconda安装的过程中，比较容易出错的环节是环境变量的配置，所以大家在配置环境变量的时候，要细心一些①安装......
  • Mybatis笔记
    如何获得Mybatis?maven仓库：<!--https://mvnrepository.com/artifact/org.mybatis/mybatis--><dependency><groupId>org.mybatis</groupId><artifactId>mybatis</artifactId><version>3.5.6</version></depende......
  • 财大ACM实验室招新指南
    财大ACM实验室招新指南ACM科普大学竞赛ACM通俗是指XCPC，也就是ICPC/CCPC。其中ICPC即InternationalCollegiateProgrammingContest，它是国际大型比赛。也在中国高等教育学会列出的榜单上。属于国际竞赛。如果能在ICPC区域赛拿到银牌、金牌。国内的一些公司可能就会向你投出......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99