AC自动机学习笔记
什么是自動機
一般指確定有限狀態(tài)自動機，所以AC自動機不是自動AC機
自動機是一個非常廣泛使用的數學模型
-
自動機是一個對信號序列進行判定的模型
解釋一下上面那句話
信號序列是指一串有順序的信號例如字符串的從前到后每一個字符
判定是指對某一個命題給出真或者假的判斷
對于自動機，一共存在3種信號序列
-
不能識別
-
判定結果為真
-
判定結果為假
-
-
自動機的結構其實是一張有向圖
其中自動機每個節(jié)點都是一個判定節(jié)點，節(jié)點只是狀態(tài)而非任務，邊可以接受多種字符
下面的是一個判斷一個二進制數是不是偶數的自動機
從起始結點開始，從高位到低位接受這個數的二進制序列，看最終停在哪里。
若最終停在紅圈結點，則是偶數，否則則反之
-
自動機只是數學模型，不是算法，不是數據結構
因此用不同的實現方法可以得到不同的復雜度
形式化定義
一個\(\text{DFA}\)(確定有限狀態(tài)自動機,即自動機)由五部分組成
-
字符集\(\sum\) :
本自動機只能輸入這些字符
-
狀態(tài)集合\(Q\) :
如果把一個\(\text{DFA}\)看成有向圖則\(\text{DFA}\)中的狀態(tài)就相當于圖上的頂點
-
起始狀態(tài)\(s\) :
對于\(s\in Q\)，\(s\)是一個特殊的狀態(tài)
-
接受狀態(tài)集合\(F\) :
對于\(F\subseteq Q\),\(F\)是一組特殊狀態(tài)
-
轉移函數\(\delta\) :
\(\delta\) 是一個接受兩個參數返回一個值的函數，其中第一個參數和返回值都是一個狀態(tài)而第二個參數是字符集\(\sum\)中的一個字符
把一個\(\text{DFA}\)看成一張有向圖，\(\text{DFA}\)中的\(\delta\)就相當于邊，每條邊上都有一個字符
\(\text{DFA}\)的作用是識別字符串，對于自動機 \(\text A\) ，若它能識別字符串 \(S\) ，那么 \(A(S)=\mathrm{T}\) ，反之\(A(S)=\mathrm{F}\) 。
當 \(DFA\) 讀入一個字符串時，從初始狀態(tài)起按照轉移函數一個一個字符地轉移。
如果讀入完一個字符串的所有字符后位于一個接受狀態(tài)，那么稱 \(DFA\) 接受 這個字符串，反之稱 \(DFA\) 不接受 這個字符串。
如狀態(tài) \(v\) 沒有字符 \(c\) 的轉移，則令 \(\delta(v,c)=\mathrm{null}\) ，而 \(\mathrm{null}\) 只能轉移到 \(\mathrm{null}\) ，且 \(\mathrm{null}\) 不屬于接受狀態(tài)集合。
無法轉移到接受狀態(tài)的狀態(tài)可以視作 \(\mathrm{null}\) ，也可以說 \(\mathrm{null}\) 代指所有無法轉移到接受狀態(tài)的狀態(tài)
我們擴展定義轉移函數 [\delta] ，令其第二個參數可以接收一個字符串： [\delta(v,s)=\delta(\delta(v,s[1]),s[2..|s|])] ，擴展后的轉移函數就可以表示從一個狀態(tài)起接收一個字符串后轉移到的狀態(tài)。那么， [A(s)=[\delta(start,s)\in F]] 。
下圖是一個接受且僅接受字符串 "\(a\)", "\(ab\)", "\(aac\)" 的 \(\text{DFA}\)：
\(\text{AC}\)自動機
AC自動機是以Trie為基礎結合KMP的思想建立的自動機
KMP算法是求單字符串對單字符串的匹配使用的,而AC自動機是求多個字符串在一個字符串上的匹配使用的
AC自動機的實現
AC自動機需要提前知道所有的需要匹配的字符串
-
第一步 把需要匹配的字符串構建成一棵Trie樹
-
第二步 對Trie樹上的所有節(jié)點構造失配指針
構建Trie樹
普通的Trie，該怎么建就怎么建
這里借用大佬的圖片
構建失配指針
\(fail\)指針在這里的作用是每次沿著Trie樹匹配，當前位置沒有匹配上時，直接跳轉到失配指針所指向的位置繼續(xù)進行匹配
在這里\(fail\)指針指向的是一個在\(\text{Trie}\)里存在的最長的與真后綴相同的字符串。
用OI-wiki的圖舉個例子
如 \(she\)，她的真后綴有 \(he\)，\(e\) 和 \(\varnothing\)，其中 \(he\) 和 \(\varnothing\) 存在于 \(\text{Trie}\) 樹中，則讓 \(9\) 號節(jié)點的 \(fail\) 指針指向最長的 \(he\) 的末尾節(jié)點 \(2\) 號節(jié)點
如 \(her\)，她的真后綴有 \(er\)，\(r\) 和 \(\varnothing\)，只有 \(\varnothing\) 存在于 Trie 樹中，則讓 \(3\) 號節(jié)點的 \(fail\) 指針指向根節(jié)點 \(0\)
如何求出失配指針
當前節(jié)點 \(p\) 代表的字符是 \(c\)，\(p\) 的 \(fail\) 指針應指向 \(p\) 的父親的 \(fail\) 指針的代表 \(c\) 的兒子
如圖，\(9\) 代表的字符是 \(e\)，\(9\) 的父親是 \(8\)，\(8\) 的 \(fail\) 指針指向 \(1\)，\(1\) 的代表 \(e\) 的兒子是 \(2\)，因此 \(9\) 的 \(fail\) 指針指向 \(2\) 號節(jié)點。
如果\(p\)不存在代表\(c\)的兒子則讓\(c\)的\(fail\)指針指向\(p\)的\(fail\)指針指向的節(jié)點\(p'\)的代表\(c\)的兒子
如OI-wiki上的圖
這里是OI-wiki上的完整動圖
- 藍色結點：BFS 遍歷到的結點 u
- 藍色的邊：當前結點下，AC 自動機修改字典樹結構連出的邊。
- 黑色的邊：AC 自動機修改字典樹結構連出的邊。
- 紅色的邊：當前結點求出的 fail 指針
- 黃色的邊：fail 指針
- 灰色的邊：字典樹的邊
我們可以以此來寫出代碼
$My\ Code$
#include<bits/stdc++.h>
using namespace std;
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
class AC{
public:
class Trie{
public:
int fail,vis[26],end;
}Tr[1000000];
int cnt;
inline void clear(){
memset(Tr,0,sizeof(Tr));
}
inline void ins(string s){
int l=s.length(),q=0;
for(int i=0;i<l;++i){
if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
q=Tr[q].vis[s[i]-'a'];
}
Tr[q].end+=1;
}
inline void Get(){
queue<int>Q;
for(int i=0;i<26;++i){
if(Tr[0].vis[i]!=0){
Tr[Tr[0].vis[i]].fail=0;
Q.push(Tr[0].vis[i]);
}
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<26;++i){
if(Tr[u].vis[i]!=0){
Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
Q.push(Tr[u].vis[i]);
}
else
Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
}
}
}
inline int Ask(string s){
int l=s.length(),q=0,ans=0;
for(int i=0;i<l;++i){
q=Tr[q].vis[s[i]-'a'];
for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
ans+=Tr[t].end;
Tr[t].end=-1;
}
}
return ans;
}
}AC;
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
string s;
int m=read();
while(m--){
int n=read();
AC.clear();
for(int i=1;i<=n;++i){
cin>>s;
AC.ins(s);
}
AC.Get();cin>>s;
write(AC.Ask(s));
puts("");
}
}
洛谷的完整題面
【模板】AC 自動機（簡單版）
題目描述
給定 \(n\) 個模式串 \(s_i\) 和一個文本串 \(t\)，求有多少個不同的模式串在文本串里出現過。
兩個模式串不同當且僅當他們編號不同。
輸入格式
第一行是一個整數，表示模式串的個數 \(n\)。
第 \(2\) 到第 \((n + 1)\) 行，每行一個字符串，第 \((i + 1)\) 行的字符串表示編號為 \(i\) 的模式串 \(s_i\)。
最后一行是一個字符串，表示文本串 \(t\)。
輸出格式
輸出一行一個整數表示答案。
樣例 #1
樣例輸入 #1
3
a
aa
aa
aaa
樣例輸出 #1
3
樣例 #2
樣例輸入 #2
4
a
ab
ac
abc
abcd
樣例輸出 #2
3
樣例 #3
樣例輸入 #3
2
a
aa
aa
樣例輸出 #3
2
提示
樣例 1 解釋
\(s_2\) 與 \(s_3\) 編號（下標）不同，因此各自對答案產生了一次貢獻。
樣例 2 解釋
\(s_1\)，\(s_2\)，\(s_4\) 都在串 abcd 里出現過。
數據規(guī)模與約定
- 對于 \(50\%\) 的數據，保證 \(n = 1\)。
- 對于 \(100\%\) 的數據，保證 \(1 \leq n \leq 10^6\)，\(1 \leq |t| \leq 10^6\)，\(1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6\)。\(s_i, t\) 中僅包含小寫字母。
例題
Keywords Search
AC自動機板子題，注意每組數據都需要對AC自動機進行\(clear\)操作
點擊查看代碼
#include<bits/stdc++.h>
using namespace std;
namespace IO{
inline void close(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);}
inline void Fire(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int s = 0,w = 1;char ch = getchar();while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}return s*w;}
inline void write(int x){char F[200];int tmp=x>0?x:-x,cnt=0;;if(x<0)putchar('-') ;while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}if(cnt==0)putchar('0');while(cnt>0)putchar(F[--cnt]);putchar(' ');}
}
using namespace IO;
class AC{
public:
class Trie{
public:
int fail,vis[26],end;
}Tr[1000000];
int cnt;
inline void clear(){
memset(Tr,0,sizeof(Tr));
}
inline void ins(string s){
int l=s.length(),q=0;
for(int i=0;i<l;++i){
if(!Tr[q].vis[s[i]-'a']) Tr[q].vis[s[i]-'a']=++cnt;
q=Tr[q].vis[s[i]-'a'];
}
Tr[q].end+=1;
}
inline void Get(){
queue<int>Q;
for(int i=0;i<26;++i){
if(Tr[0].vis[i]!=0){
Tr[Tr[0].vis[i]].fail=0;
Q.push(Tr[0].vis[i]);
}
}
while(!Q.empty()){
int u=Q.front();
Q.pop();
for(int i=0;i<26;++i){
if(Tr[u].vis[i]!=0){
Tr[Tr[u].vis[i]].fail=Tr[Tr[u].fail].vis[i];
Q.push(Tr[u].vis[i]);
}
else
Tr[u].vis[i]=Tr[Tr[u].fail].vis[i];
}
}
}
inline int Ask(string s){
int l=s.length(),q=0,ans=0;
for(int i=0;i<l;++i){
q=Tr[q].vis[s[i]-'a'];
for(int t=q;t&&Tr[t].end!=-1;t=Tr[t].fail){
ans+=Tr[t].end;
Tr[t].end=-1;
}
}
return ans;
}
}AC;
signed main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
string s;
int m=read();
while(m--){
int n=read();
AC.clear();
for(int i=1;i<=n;++i){
cin>>s;
AC.ins(s);
}
AC.Get();cin>>s;
write(AC.Ask(s));
puts("");
}
}
下面是花絮
總結
- 上一篇： Vite4+Typescript+Vue
- 下一篇： 苹果fd开头是什么版本