Skip to main content

自动机

参考资料​

AC 自动机​

AC 自动机（Aho–Corasick Automaton）以 Trie 为骨架，结合 KMP 的失配指针思想，用于多模式串匹配。

建立过程分两步：将所有模式串插入 Trie；再用 BFS 对每个结点构造 fail 指针，使其指向该结点对应字符串的最长后缀状态。构建完成后同时将 Trie 改造为字典图——若字符 cc 的子结点不存在，则令其指向 fail 结点的 cc 子结点，保证每次转移 O(1)O(1)。查询时在字典图上逐字符转移，沿 fail 链累加匹配计数。设模式串总长为 ∑∣si∣\sum|s_i|，文本串长为 ∣S∣|S|，字符集大小为 ∣Σ∣|\Sigma|，构建复杂度为 O(∑∣si∣⋅∣Σ∣)O(\sum|s_i|\cdot|\Sigma|)，查询复杂度为 O(∣S∣⋅∣Σ∣)O(|S|\cdot|\Sigma|)（连字典图后）。

930 Bcpp
#include <bits/stdc++.h>
using namespace std;

const int N=1000005;
int son[N][26],fail[N],cnt[N];
int tot=0;
void insert(string s)
{
	int u=0;
	for(auto c:s)
	{
		int x=c-'a';
		if(!son[u][x])son[u][x]=++tot;
		u=son[u][x];
	}
	cnt[u]++;
}
void build()
{
	queue<int> q;
	for(int i=0;i<26;i++)
		if(son[0][i])q.push(son[0][i]);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			if(son[u][i])
			{
				fail[son[u][i]]=son[fail[u]][i];
				q.push(son[u][i]);
			}
			else
			{
				son[u][i]=son[fail[u]][i];
			}
		}
	}
}
int query(string s)
{
	int u=0,res=0;
	for(auto c:s)
	{
		u=son[u][c-'a'];
		for(int j=u;j&&cnt[j]!=-1;j=fail[j])
		{
			res+=cnt[j];
			cnt[j]=-1;
		}
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		string s;
		cin>>s;
		insert(s);
	}
	build();
	string t;
	cin>>t;
	cout<<query(t)<<'\n';
	return 0;
}

后缀数组简介​

后缀数组（Suffix Array，SA）把字符串的所有后缀按字典序排序，saisa_i 为排名第 ii 的后缀起点，rkrk 为其逆。常用倍增法 O(nlog⁡n)O(n\log n) 构建，也有 SA-IS 等 O(n)O(n) 做法。

配合 height 数组（排名相邻两后缀的最长公共前缀），后缀数组能解决本质不同子串数、可重叠/不可重叠最长重复子串等一类子串问题。

后缀自动机​

后缀自动机（Suffix Automaton，SAM）是能接受一个字符串所有后缀的最小确定有限自动机。它的每个状态对应一组 endpos⁡\operatorname{endpos}（结束位置集合）相同的子串，状态数与转移数都是 O(n)O(n)，可在线 O(n)O(n) 构建。

借助 parent⁡\operatorname{parent} 树（按 endpos⁡\operatorname{endpos} 的包含关系）与各状态的 len⁡\operatorname{len}，SAM 能高效解决本质不同子串计数、子串出现次数、两串最长公共子串等问题。

广义后缀自动机​

广义后缀自动机 是后缀自动机在多个字符串上的推广，能接受一组字符串的所有后缀。把所有串建成一棵 Trie 后在其上构建，或逐串插入时在已有转移处特判，即得一个大小为 O(∑∣s∣)O(\sum|s|) 的自动机，可统计多串的本质不同子串等。

例题​

洛谷 P3808 AC 自动机（简单版）

给定 nn 个模式串 sis_i 和一个文本串 tt，求有多少个不同的模式串在文本串里出现过。 两个模式串不同当且仅当他们 编号 不同。

洛谷 P3796 AC 自动机（简单版 II）

有 NN 个由小写字母组成的模式串以及一个文本串 TT。每个模式串可能会在文本串中出现多次。你需要找出 哪些 模式串在文本串 TT 中出现的次数最多。

洛谷 P5357 【模板】AC 自动机

给你一个文本串 SS 和 nn 个模式串 T1∼nT_{1\sim n}，请你分别求出每个模式串 TiT_i 在 SS 中出现的次数。

洛谷 P3809 【模板】后缀排序

给定一个长度为 nn 的字符串，求其后缀数组，即把所有后缀按字典序升序排序后，各后缀的起始下标。

洛谷 P3804 【模板】后缀自动机（SAM）

给定一个仅含小写字母的字符串 ss，在所有出现次数不小于 22 的子串中，求「出现次数 ×\times 子串长度」的最大值。

洛谷 P6139 【模板】广义后缀自动机（广义 SAM）

给定 nn 个仅含小写字母的字符串，求这些字符串中本质不同的子串个数。