前言
筆者之前說最近自己不會碰字符串瞭，結果還是打臉瞭。我們來學學AC自動機。
我想大傢第一次看見這個名字的時候都在想：怎麼還有能自動AC程序的“自動機”？
這又是什麼高手瞭
放心，競賽裡面顯然是沒有這種東西的。
AC，眾所周知可能是很多東西的簡寫，至少包括：
Air-Conditoner(空調)
Alternating Current (交流電);
Assassin's Creed(遊戲《刺客信條》);
（某些意義上，這算不算一種哈希沖突？我覺得是，我們在這裡建立瞭一個字符串與每個單詞之間首字母的映射。）
在這裡，AC自動機的全稱是Aho-Corasick automaton，其中的Aho是Alfred Aho，也是那本《龍書》（《編譯原理》）的作者之一。不得不說大佬就是大佬啊。
事實上筆者很好奇AC自動機與KMP算法的關系。筆者查閱資料時發現AC自動機的提出甚至早於KMP算法的發表，因此我猜Aho和Corasick在構思時應該不大可能是基於“在字典樹上進行KMP算法”這一想法而提出AC自動機。不過我們姑且認為它們有關系吧。
正文
引入
除非特殊說明，下文所有下標從0開始為什麼要有AC自動機？
讓我們復習一下KMP算法。KMP算法中存在一個模式串與一個匹配串，在匹配串中尋找模式串。如何我們有多個模式串我們該怎麼匹配呢？我們肯定會想到用KMP來暴力匹配每一個字符串。之前筆者做的這道題https://www.luogu.com.cn/problem/P1470就是用這種方法做的並且通過瞭。
在AC自動機中我們用trie來儲存所有的字符串。但是僅僅靠trie是不能做到字符串的多模式匹配的，因此我們還需要對trie進行改造。
我們可以知道，如果B字符串是A字符串的後綴，那麼如果A字符串在匹配串中出現瞭，B字符串一定在匹配串中出現瞭。舉個例子（本人畫圖技術很差，恭請諒解。節點6是後面加的，所以順序不太對）：
如果我們有一個如下的trie，紅色節點代表一個模式串。
比如說我們要在這個自動機裡面嘗試尋找字符串"baab"中出現瞭哪些模式串。我們先設一個指針i，用來在trie上進行移動，把它用黃色來標記。
當字符串的下標為0，我們發現節點0到節點3之間存在一條權值為b（其實是b-'a'）的邊，因此我們考慮轉移過去（如下圖）。
當字符串的下標到瞭1，我們發現節點3和節點4之間存在一條權值為a的邊，我們繼續轉移過去——但，我們是不是漏掉瞭什麼？是的，我們漏掉瞭“a”這個字符串。我們想，要是有什麼辦法能把字符串“ba”的後綴給“一網打盡”就好瞭。怎麼辦呢？直接把i指針移動到祖先的另一顆子樹上不太可行，我們再搞一個指針j，用綠色來表示，就用它來檢查當前字符串中已經吧。順便，我們構造一條節點4到節點1的邊。（如下圖）
說明：這裡並不是記錄所有的後綴，而是記錄所有出現在瞭充當其他字符串前綴的後綴。怎麼理解呢？假如我們有兩個模式串“abc”、“c”，“c”是“abc”的真後綴，那麼"abc"中的'c'後面那個節點應該存在一條指向"c"中'c'後面那個節點的邊，但並不需要指向"bc"，因為沒有字符串以"bc"開頭。
這樣我們就匹配到瞭字符串“a”。
當字符串的下標為2，我們發現節點4到節點5之間存在一條權值為a的邊，因此我們考慮轉移過去（如下圖）。考慮到這個時候我們也能匹配到字符串aa（盡管字符串“aa”並不是模式串），我們繼續仿照之前進行連邊。此時此刻我們匹配到瞭字符串“baa”。（如下圖）
那麼，如果我們匹配失敗該怎麼辦呢？我們此時此刻已經走到盡頭瞭，但我們在KMP算法裡早就知道瞭，很多高效的字符串算法恰恰依賴的是“永不後退”。我們發現隔壁子樹上不是有“aab”這個字符串嗎？我們直接建一條邊轉移過去就好瞭。這樣我們就匹配到瞭字符串aab（如下圖）
啊？你可能感到很疑惑——雖然很合情理，我們是怎麼做到這一點的？
瑟瑟發抖
原理講解
如圖，在AC自動機中存在兩種邊:綠色的邊和黑色的邊。而如同我們剛剛演示的過程，黑色的邊也可以分為兩種：一種是一開始就存在在trie上的樹邊，另一種是我們後面添加的邊。這裡我們引用董曉老師的講解https://www.bilibili.com/video/BV1tF41157Dy/?spm_id_from=333.337.search-card.all.click&vd_source=d9b89a11011b83051a736249d783bb8a，我們把綠色的邊稱為回跳邊，後面加上的那種邊叫做轉移邊。該自動機正是通過不斷添加這兩種邊來完成的。
在構建AC自動機時，我們枚舉訪問到的節點的所有出邊（邊權字符集中的所有字符，在這裡是'a'-'z'）。假如說某邊權存在對應的節點，即代表某種轉移是合法的，我們就給下面那個節點構建回跳邊。具體是怎麼建立的呢？我們引用董老師的圖。
我們建立一條從兒子到父親的回跳邊指向的節點的兒子的回跳邊
這個看起來很抽象，實際上它是為瞭方便我們後續的“一網打盡”。
一網打盡！
為什麼這麼說呢？我們首先假設回跳邊指向的節點對應的字符串代表該節點對應字符串的一個真後綴，即ne[u]是u的一個真後綴，那麼如果我們在這兩個字符串後面添加一個相同的字母，添加過後的字符串應當同樣滿足此關系。使用數學歸納法應該可以證明，由於筆者水平問題就不證明瞭。可以看出，以0節點為根的兩個子樹如果存在這樣的“交叉部分”（如下圖），則說明如果我們匹配瞭某字符串的一部分且trie中存在這樣的“平行四邊形”，我們肯定匹配瞭另外一個字符串的前綴。這為我們接下來的部分打下瞭基礎。
其他的回跳邊呢？它們都被賦值成0瞭，沒畫。
介於做真後綴的字符串應該比較短，我們很自然地想到整個算法過程應該是在trie上BFS得到的——由於BFS的特性，下層節點一定比上層節點後訪問。結合引入部分的例子應該不難理解瞭——如果還是不能理解應該是筆者的文章寫得不夠深入淺出或者理解不足，畢竟筆者水平不夠。
那麼如果兒子不存在呢？我們要準備跑路瞭。
跑瞭跑瞭
如果兒子不存在，我們就考慮轉移到其他子樹上。可以看到，我們之前已經證明過瞭（大概）回跳邊指向的是該節點對應字符串的一個真後綴，那麼我們就跳過去，看看它接下來的那一部分是否能與匹配串匹配，接下來循環此過程即可。
這裡可以看出AC自動機和KMP很像瞭，特別是在回跳這一點上。當然我個人覺得它們還是有點區別的。
代碼
#include<iostream>
#include<queue>
using namespace std;
const int Max=1e6+1;
queue <int> q;
int trie[Max][26],tot,cnt[Max],ne[Max];
void insert(string a){
int p=0;
for(int i=0;i<a.length();i++){
if(!trie[p][a[i]-'a']){
trie[p][a[i]-'a']=++tot;
}
p=trie[p][a[i]-'a'];
}
cnt[p]++;
//cout<<p<<endl;
}
void build(){
//q.push(0); 大傢切記不能這麼寫，這裡不能從0開始搜索。
//因為所有邊的回跳邊都默認為0，如果從0開始就會把與0相連的節點的回跳邊賦值為 它本身。
for(int i=0;i<26;i++){
if(trie[0][i]){
q.push(trie[0][i]);
}
}
while(q.size()){
int x=q.front();q.pop();
for(int i=0;i<26;i++){
if(trie[x][i]){
q.push(trie[x][i]);
ne[trie[x][i]]=trie[ne[x]][i];
// cout<<trie[x][i]<<" "<<trie[ne[x]][i]<<" "<<ne[x]<<endl;
}else{
trie[x][i]=trie[ne[x]][i];
}
}
}
}
int query(string t){
int p=0;
int ans=0;
for(int i=0;i<t.length();i++){
p=trie[p][t[i]-'a'];
//cout<<p<<endl;
for(int j=p;j&&~cnt[j];j=ne[j]){ //沿回跳邊不斷轉移，其中~cnt[j]指的是如果為-1就表示被匹配成功過，不必繼續搜索
ans+=cnt[j];
//cout<<j<<" "<<ne[j]<<" "<<ans<<endl;
cnt[j]=-1;//打標記
}
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
string str;
cin>>str;
insert(str);
}
build();
string t;
cin>>t;
cout<<query(t);
}