再学串串（二）：AC 自动机不是自动 AC 机
过去的章节
再学串串（一）：我真的学会 KMP 了吗？评「clx201022 式的傲慢」
关于上一章节 KMP 与「周期」的有关内容：「周期」的概念与接下来的内容联系较浅，秉承着相信读者水平的原则，在此就不多赘述。（有关结论与证明具体可见后文 友链 部分）
第二站：初识自动机
有限状态自动机（Finite State Machine，FSM，以下也简称自动机）是最简单的一类计算模型，体现在它的描述能力与资源都极其有限．自动机广泛应用在 OI、计算机科学中，其思想在许多字符串算法中都有涉及，因此推荐在学习一些字符串算法（KMP、AC 自动机、SAM）前先完成自动机的学习．
自动机严谨的定义依赖的数学模型于 OI Wiki 已有详细讲解，此处就不多赘述了。
任意自动机
M 可以被理解为一个有向图：点是状态，其中有一些点是接受状态，每个点的每条边上都有着一个字符c ，代表状态转移。从起始状态q 开始，依次按照字符串s 的每个字符走，最后如果在接受状态就称M 接受s ，否则称M 不接受s 。
对于没有对应字符的状态转移的情况，可以视作一个无法到达任何接受状态的失配状态。
可将字符串
实际应用时，因为情况复杂，难以以接受或不接受的二元状态划分，往往会根据当前所在的状态再做统计处理。
状态转移这个词在动态规划相关内容中出现频率也相当高。这并不是巧合。事实上，很多时候建模一个自动机的目的就是为了在上面进行动态规划。
:::info[如果您还没有理解自动机]
奶茶自动机 是个不错的例子。
下文还有另一个例子：
《三国》兵法有云：「胜兵必骄，骄兵必败，败兵必哀，哀兵必胜。」
而这句话就可以被建模为一个兵法自动机：
（省略了「兵」字）
一般地，将胜兵定义为接受状态。
随着星夜流转，四种状态间能自然地相互转移；而其中的一些突发事件就可以理解为状态间的其他转移路径。
如经典的博望坡战役中，刘备一方原先是哀兵，但诸葛亮计划立 flag，成了骄兵。
其开战后经过星夜本应为败兵，然而天意扭曲。所以最后的转移到的结果是刘备一方获得了博望坡战役的胜利。
再看刘备伐吴。
一开始，蜀汉一方是哀兵，而哀兵必胜。所以经过星夜流转，蜀汉成了了胜兵状态，而胜兵必骄，蜀汉转移到骄兵状态。
东吴一方一开始是骄兵状态，星夜流转，败给蜀汉一方后转移到败兵状态，又随星夜流转，转移到了哀兵状态，而哀兵必胜，成为了胜兵。
此时东吴方本应根据胜兵必骄原则，成为骄兵，又骄兵必败，输下整场战役。
但陆逊不愧为东吴第四任大都督陆逊。每次东吴由胜兵到骄兵时，他采取固守不出的策略，将骄兵转移为了哀兵，从而继续成为胜兵，屡战屡胜。
最后，随着夷陵之火，这场伐吴之战由蜀吴两方两败俱伤收尾。
（点此播放背景音乐）
字符串自动机与此大同小异，区别仅为将由时间顺序排列的历史事件换为了从前到后排列的字符串的每个字符。
:::
Trie
Trie 的名称经过多方搜索，较大可能来自于英文单词 retrieval 中的一个子串或英文单词 tree 的一个子序列，也有可能与两者都有关。
其作用为对于一个字符串集合
相比于挨个比较，其主要的优化为将前缀相同的字符串相同的前缀合并，可将
字典树 Trie 在图论意义下是一棵树——其每个状态
实现方面对于录入时每个点记录其所能转移到的状态并更新接受状态，查询时直接跑自动机。
无法到达接受状态的状态统一视为失配状态，到达失配状态时直接返回不接受。
:::success[三年前写的模板题代码]
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=1e5+10;
inline string read_string()
{
char ch;
string s;
int cnt=0;
while((ch=getchar())!='\n')
{
s[cnt++]=ch;
}
}
struct trie
{
int nex[MAXN<<2][26+1]={0};
int cnt=0;
int exist[MAXN<<2]={0};
void insert(char *s)
{
int p=0;
int l=strlen(s);
for(int i=0;i<l;i++)
{
int c=s[i]-'a';
if(!nex[p][c])nex[p][c]=++cnt;
p=nex[p][c];
}
exist[p]++;
}
int find(char *s)
{
int p=0;
int l=strlen(s);
for(int i=0;i<l;i++)
{
int c=s[i]-'a';
if(!nex[p][c])return 0;
p=nex[p][c];
}
return exist[p]++;
}
}trie;
int n,m;
char sss[51];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>sss;
trie.insert(sss);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
cin>>sss;
int opt=trie.find(sss);
if(opt==0)printf("WRONG\n");
if(opt==1)printf("OK\n");
if(opt>1)printf("REPEAT\n");
}
return 0;
}:::
KMP 自动机
有些人觉得 AC 自动机就是在 Trie 上做 KMP，但还有些人不以为然。这个矛盾的根本，或者说根本的矛盾又在哪呢？
根本矛盾就是 KMP 自动机 这一概念在学习关系中的缺位。
学 AC 自动机前不学 KMP 自动机就想理解透彻，可谓是绪山真寻喝可乐——无稽之谈。
KMP 自动机做的事很简单：在 KMP 算法的基础上，对于一个字符串
如同 KMP，KMP 自动机也可以轻松地进行字符串匹配。因为对于字符串
因此，将
构造一个自动机
以 abacaba 为例。
（
首先对于一个串，它自己肯定是自己的后缀。（显然）
然后贪心地考虑如何让文本串
可以发现事实上只要求
对于每个状态考虑其如何转移：因为其已经是当前最长能匹配到的
但如果没匹配上呢？比如现在已经匹配到了
此时考虑利用 KMP 中的
如果最后都没有匹配成功呢？此时不能认为直接进入失配状态，因为只考虑后缀，所以后面再加上一串
本质上就是把 KMP 算法搬到了自动机上，但因为其建模为了自动机，所以往往能以更优的复杂度完成特定问题。
形式化定义看这里。
如 KMP 自动机模板题 CF1721E Prefix Function Queries。
:::success[模板代码]
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 100;
string s;
size_t nxt[maxn + 1][26], fails[maxn + 1], n;
// border 即匹配了多长
void get_fail()
{
for(int i = 0; i < n; i++)
{
fails[i] = (i ? nxt[fails[i - 1]][s[i] - 'a'] : 0);
// 这一位失配了，即当成前面失配了再看下一位
for(int k = 0; k < 26; k++)
{
if(s[i] - 'a' == k) nxt[i][k] = i + 1;
// nxt 即可匹配字符，由于是 0-index，所以比目前下标大 1
else nxt[i][k] = (i ? nxt[fails[i - 1]][k] : 0);
// 其他的当失配了做即可
}
}
}
int q;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> s;
n = s.size();
get_fail();
cin >> q;
while(q--)
{
string t;
cin >> t;
size_t m = t.size();
for(size_t i = n; i < n + m; i++)
{
fails[i] = (i ? nxt[fails[i - 1]][t[i - n] - 'a'] : 0);
for(int k = 0; k < 26; k++)
{
if(t[i - n] - 'a' == k) nxt[i][k] = i + 1;
else nxt[i][k] = (i ? nxt[fails[i - 1]][k] : 0);
}
cout << fails[i] << ' ';
}
cout << endl;
}
return 0;
}:::
如果直接用一般 KMP 求，基于均摊的复杂度难以得到保证，所以要用 KMP 自动机带上一个
聪明的读者可以发现上一篇文章中的 失配树 就是按照失配指针把 状态 提成一棵树构造而成的。
AC 自动机
学会 AC 自动机需要注意的只有两点：它是 KMP 自动机在 Trie 上的自然推广；以及 AC 自动机跟自动 AC 机并没有任何关系。[^acam]唯一区别是
对于状态
（设原字典树上的转移函数为
动用人类智慧，发现
多字符串带来的还有一个困境：一个串可能是另一个串的后缀，此时如何统计？
对于以上问题，不同的题会有不同的解决办法，如下列三道题每题都会有不同的统计方法。
P3808 AC 自动机（简单版）
按
:::success[Accepted]
#include<bits/stdc++.h>
using namespace std;
class Aho_Corasick_Automaton
{
typedef unsigned index_type;
typedef unsigned cnt_type;
typedef int mark_type;
private :
struct fsm_state // 自动机的每个状态
{
unordered_map<char, index_type> to;
// 自动机转移路径
index_type fail;
// fail 即失配状态
cnt_type fail_in;
// topu 排序可用
basic_string<mark_type> mark;
// 每个状态上的若干标记（一个点上可能有多个
bool vis;
fsm_state() : fail(0), fail_in(0), vis(0){} // 初始化
};
static constexpr index_type root = 1;
index_type lst_id;
fsm_state st[2000001];
protected :
index_type push_new()
{
st[++lst_id] = fsm_state();
return lst_id;
}
// 加入一个新节点
public :
Aho_Corasick_Automaton() : lst_id(0)
{
st[++lst_id] = fsm_state();
}
// 1 作为根节点
Aho_Corasick_Automaton & insert(const string & s, const mark_type flag)
{
index_type u = root;
const size_t slen = s.size();
for (size_t i = 0; i < slen; i++)
{
if (!st[u].to.count(s[i])) // 找不到 s[i]
{
st[u].to[s[i]] = push_new(); // 新建一个
}
u = st[u].to[s[i]];
// 继续往后走
} st[u].mark.push_back(flag);
// 存一个标记 - 该节点有一个 flag 子串
return * this;
}
Aho_Corasick_Automaton & get_fail_in()
{
for (size_t i = root; i <= lst_id; i++)
{
st[i].fail_in = cnt_type(0);
}
for (size_t i = root; i <= lst_id; i++)
{
++st[st[i].fail].fail_in;
}
return * this;
}
// 得到 fail 树上的入度
index_type get_tran_to(index_type u, char c)
{
index_type fail_zzz = u, ret = root, zzz2 = u;
while (fail_zzz != root && !st[fail_zzz].to.count(c))
{
fail_zzz = st[fail_zzz].fail;
}
// 往下不停寻找
if (st[fail_zzz].to.count(c))
{
ret = st[fail_zzz].to[c];
}
// 不然就只能回到 root 了
while (zzz2 != fail_zzz && zzz2)
{
st[zzz2].to[c] = ret;
zzz2 = st[zzz2].fail;
}
// u 一直到 fail_zzz 上的每个到 c 的路径都可以优化
return ret;
}
Aho_Corasick_Automaton & get_fail()
{
queue<index_type> q;
st[root].fail = 0;
// 空
index_type u = root;
for (char c = 'a'; c <= 'z'; c++)
{
if (st[u].to.count(c))
{
st[st[u].to[c]].fail = root;
q.push(st[u].to[c]);
}
}
// 只算存在的点
while (!q.empty())
{
u = q.front();
q.pop(); // 去一个出来
for (char c = 'a'; c <= 'z'; c++)
{
if (st[u].to.count(c))
{
st[st[u].to[c]].fail = get_tran_to(st[u].fail, c);
q.push(st[u].to[c]);
}
}
}
return get_fail_in();
}
unordered_map<mark_type, cnt_type> query(const string & s)
{
unordered_map<mark_type, cnt_type> wer;
index_type u = root;
const size_t slen = s.size();
for (size_t i = 0; i < slen; i++)
{
u = get_tran_to(u, s[i]);
// 这个地方匹配到
for (index_type z = u; !st[z].vis && z; z = st[z].fail)
{
for (auto i : st[z].mark)
{
wer[i]++;
}
st[z].vis = 1;
}
}
return wer;
}
} ac;
using namespace std;
const int maxn = 1e6;
int n;
string T[maxn + 1], S;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> T[i];
ac.insert(T[i], i);
} ac.get_fail();
cin >> S;
auto wer = ac.query(S);
int cnt = 0;
for (int i = 1; i <= n; i++)
{
cnt += (wer[i] ? 1 : 0);
}
cout << cnt << endl;
return 0;
}:::
P5357 【模板】AC 自动机
要求先统计匹配过程中经过每个点的次数（即对于每个点，求对于每个前缀经过的次数的总和）然后再拓补优化做。
:::success[Accepted]
#include<bits/stdc++.h>
using namespace std;
class Aho_Corasick_Automaton
{
typedef unsigned index_type;
typedef unsigned cnt_type;
typedef int mark_type;
private :
struct fsm_state // 自动机的每个状态
{
unordered_map<char, index_type> to;
// 自动机转移路径
index_type fail;
// fail 即失配状态
cnt_type fail_in;
// topu 排序可用
vector<mark_type> mark;
// 每个状态上的若干标记（一个点上可能有多个）
fsm_state() : fail(0), fail_in(0){} // 初始化
};
static constexpr index_type root = 1;
index_type lst_id;
fsm_state st[200001];
protected :
index_type push_new()
{
st[++lst_id] = fsm_state();
return lst_id;
}
// 加入一个新节点
public :
Aho_Corasick_Automaton() : lst_id(0)
{
st[++lst_id] = fsm_state();
}
// 1 作为根节点
Aho_Corasick_Automaton & insert(const std::string & s, const mark_type flag)
{
index_type u = root;
const size_t slen = s.size();
for (size_t i = 0; i < slen; i++)
{
if (!st[u].to.count(s[i])) // 找不到 s[i]
{
st[u].to[s[i]] = push_new(); // 新建一个
}
u = st[u].to[s[i]];
// 继续往后走
}
st[u].mark.emplace_back(flag); // 存一个标记 - 该节点有一个 flag 子串
return * this;
}
Aho_Corasick_Automaton & get_fail_in()
{
for (size_t i = root; i <= lst_id; i++)
{
st[i].fail_in = cnt_type(0);
}
for (size_t i = root; i <= lst_id; i++)
{
++st[st[i].fail].fail_in;
}
return * this;
}
// 得到 fail 树上的入度
index_type get_tran_to(index_type u, char c)
{
index_type fail_zzz = u, ret = root, zzz2 = u;
while (fail_zzz != root && !st[fail_zzz].to.count(c))
{
fail_zzz = st[fail_zzz].fail;
}
// 往下不停寻找
if (st[fail_zzz].to.count(c))
{
ret = st[fail_zzz].to[c];
}
// 不然就只能回到 root 了
while (zzz2 != fail_zzz && zzz2)
{
st[zzz2].to[c] = ret;
zzz2 = st[zzz2].fail;
}
// u 一直到 fail_zzz 上的每个到 c 的路径都可以优化
return ret;
}
Aho_Corasick_Automaton & get_fail()
{
queue<index_type> q;
st[root].fail = 0;
// 空
index_type u = root;
for (char c = 'a'; c <= 'z'; c++)
{
if (st[u].to.count(c))
{
st[st[u].to[c]].fail = root;
q.push(st[u].to[c]);
}
}
// 只算存在的点
while (!q.empty())
{
u = q.front();
q.pop(); // 去一个出来
for (char c = 'a'; c <= 'z'; c++)
{
if (st[u].to.count(c))
{
st[st[u].to[c]].fail = get_tran_to(st[u].fail, c);
q.push(st[u].to[c]);
}
}
}
return get_fail_in();
}
unordered_map<mark_type, cnt_type> query(const string & s)
{
vector<cnt_type> ans(lst_id + 1, 0);
unordered_map<mark_type, cnt_type> wer;
index_type u = root;
const size_t slen = s.size();
for (size_t i = 0; i < slen; i++)
{
u = get_tran_to(u, s[i]);
++ans[u];
// 这个地方匹配到
}
// 预处理
queue<index_type> q;
for (index_type i = root; i <= lst_id; i++)
{
if (st[i].fail_in == 0)
{
q.push(i);
}
}
while (!q.empty())
{
index_type u = q.front();
q.pop();
if (!u) continue; // 忽略空节点
for (mark_type pp : st[u].mark)
{
wer[pp] += ans[u];
}
// 这个标记对应的点做一个贡献
ans[st[u].fail] += ans[u];
if (--st[st[u].fail].fail_in == 0)
{
q.push(st[u].fail);
}
}
// 拓扑
get_fail_in();
return wer;
}
} ac;
using namespace std;
const int maxn = 2e5;
int n;
string T[maxn + 1], S;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> T[i];
ac.insert(T[i], i);
} ac.get_fail();
cin >> S;
ac.query(S);
const auto wer = ac.query(S);
for (int i = 1; i <= n; i++)
{
cout << wer.at(i) << endl;
}
return 0;
}:::
P14363 [CSP-S 2025] 谐音替换
统计需要先把
（警示后人大合集）
:::success[Accepted]
#include<bits/stdc++.h>
using namespace std;
const int maxL = 5e6;
class Aho_Corasick_Automaton
{
typedef unsigned index_type;
typedef unsigned cnt_type;
typedef int mark_type;
private :
static constexpr index_type root = 1;
index_type lst_id;
index_type to[maxL + 1][27];
index_type fail[maxL + 1];
mark_type mark[maxL + 1];
protected :
index_type push_new()
{
return ++lst_id;
}
// 加入一个新节点
public :
Aho_Corasick_Automaton() : lst_id(0)
{
push_new();
}
// 1 作为根节点
Aho_Corasick_Automaton & insert(const string & s, const mark_type flag)
{
index_type u = root;
const size_t slen = s.size();
for (size_t i = 0; i < slen; i++)
{
if (!to[u][s[i] - 'a']) // 找不到 s[i]
{
to[u][s[i] - 'a'] = push_new(); // 新建一个
}
u = to[u][s[i] - 'a'];
// 继续往后走
}
mark[u] += flag;
// 存一个标记 - 该节点有一个 flag 子串
return * this;
}
index_type get_tran_to(index_type u, char c)
{
c -= 'a';
index_type fail_zzz = u, ret = root, zzz2 = u;
while (fail_zzz != root && !to[fail_zzz][c])
{
fail_zzz = fail[fail_zzz];
}
// 往下不停寻找
if (to[fail_zzz][c])
{
ret = to[fail_zzz][c];
}
// 不然就只能回到 root 了
while (zzz2 != fail_zzz && zzz2)
{
to[zzz2][c] = ret;
zzz2 = fail[zzz2];
}
// u 一直到 fail_zzz 上的每个到 c 的路径都可以优化
return ret;
}
Aho_Corasick_Automaton & get_fail()
{
queue<index_type> q;
fail[root] = 0;
// 空
index_type u = root;
for (char c = 'a' - 'a'; c <= '{' - 'a'; c++) // }
{
if (to[u][c])
{
fail[to[u][c]] = root;
q.push(to[u][c]);
}
}
// 只算存在的点
while (!q.empty())
{
u = q.front();
q.pop(); // 去一个出来
mark[u] += mark[fail[u]];
for (char c = 'a' - 'a'; c <= '{' - 'a'; c++) // }
{
if (to[u][c])
{
fail[to[u][c]] = get_tran_to(fail[u], c + 'a');
q.push(to[u][c]);
}
}
}
return *this;
}
mark_type query(const string & s)
{
mark_type wer;
index_type u = root;
const size_t slen = s.size();
wer += mark[u];
for (size_t i = 0; i < slen; i++)
{
u = get_tran_to(u, s[i]);
// 这个地方匹配到
wer += mark[u];
}
return wer;
}
} ac;
using ll = long long;
const int maxn = 2e5, maxq = 2e5;
int n, q;
string merge(const string & s1, const string & s2)
{
string s;
int loc1 = 0, loc2 = (int)s1.size() - 1;
for (int j = 0; j < (int)s1.size(); j++)
{
if (s1[j] != s2[j])
{
loc1 = j;
break;
}
}
for (int j = (int)s1.size() - 1; j >= 0; j--)
{
if (s1[j] != s2[j])
{
loc2 = j;
break;
}
}
s += s1.substr(0, loc1);
s += '{';
// }
s += s1.substr(loc1, loc2 - loc1 + 1);
s += s2.substr(loc1, loc2 - loc1 + 1);
s += '{';
// }
s += s2.substr(loc2 + 1);
return s;
}
int main()
{
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
std::string s1, s2;
cin >> s1 >> s2;
assert(s1.size() == s2.size());
if (s1 == s2)
continue;
ac.insert(merge(s1, s2), 1);
// s1!=s2 因此不用担心越界
}
ac.get_fail();
for (int j = 1; j <= q; j++)
{
std::string t1, t2;
cin >> t1 >> t2;
if (t1.size() != t2.size())
{
cout << 0 << endl;
continue;
}
assert(t1 != t2);
cout << ac.query(merge(t1, t2)) << endl;
// t1!=t2 因此不用担心越界
}
return 0;
}:::
友链
- 《周期引理及其证明》，@b6e0_
- 《浅谈有限状态自动机及其应用》，徐哲安
- 《从零开始发明 AC 自动机 / P5357 【模板】AC 自动机 题解》，@August_Light
- 《学习笔记：KMP 自动机》，@喵仔牛奶
创作声明
本文遵循 CC BY-NC-SA 4.0 协议。
保证本文未使用任何 AI 工具辅助创作。
转载例如下：
原文作者为 clx201022，转载人保证会遵循 CC BY-NC-SA 4.0 协议：以适当的方式署名，不以盈利为目的进行转载，并以相同方式共享此文。
[^acam]: AC 自动机不能让你自动 AC，相反，它可能会自动使你 WA。类比于上海爱丽丝幻乐团不在上海，没有爱丽丝，更不是幻乐团；徐州城不是城，不在中原，更不是第一雄关。