◇學時·10 & 模板·3◇ AC自動機

跟著高中上課……講AC自動機的擴展運用。然而連KMP、trie字典樹都不怎么會用的我一臉懵逼<(＿　＿)>

花一上午自學了一下AC自動機 QwQ

---

? Trie樹

字典樹的一種（聽說還有其他字典樹，不清楚）。每個節點代表一個字母，根節點相當于超級源點，根節點不表示字母。Trie樹最大的特點是從根節點出發，沿著樹邊向下走，走過的節點會形成一個字符串。而一些節點是某一個單詞的結尾，對于這種節點，我們一般會給它做一個標記（ovr）。

? 構建Trie樹（Build）

根據Trie樹的特點，最初的樹是一個空集，只包含根節點。當我們要向樹中插入一個單詞str時，從根節點出發，如果根節點有表示str[0]的兒子，則移步到該兒子；否則新建立一個表示str[0]的兒子，再移步。以此類推，當我們要插入str[k]時，我們應該在第(k+1)層的某一個節點now（根節點為第一層），如果節點now有表示str[k]的兒子，則移步，否則先創建表示str[k]的兒子，再移步。直到將整個單詞遍歷完才結束。假設我們結束時的節點在now，那么ovr可以做兩種基本的標記：① 該節點是多少個單詞的結尾；② 該節點是哪一個單詞的結尾……當然如果題目有一些奇怪的要求的話可以用ovr存儲一些奇怪的東西，甚至多定義幾個ovr也可以。

void Build(string str,int id){int len=str.length(),now=0; //當前節點是now，trie[0]是根節點for(int i=0;i<len;i++){if(!trie[now].son[str[i]-'a'])trie[now].son[str[i]-'a']=++cnt; //cnt類似于指針，用于新建節點，(cnt+1)指向最近的一個空節點now=trie[now].son[str[i]-'a']; //移步}trie[now].ovr=id; //做標記，這里是存儲的trie[now]是哪一個單詞的結尾 }

? 與AC自動機的關系

AC自動機是建立在Trie樹上的，只是圍繞KMP的fail函數增添了一些邊。

---

? KMP

一種字符串匹配算法，在樸素的字符串匹配算法的基礎上進行了可觀的優化。若要在字符串A里查找字符串B，則稱A為“主串”，B為“模式串”，當我們嘗試一次匹配時發現匹配失敗，則稱為“失配”。

匹配時有兩個指針，i表示從主串的第i個位置開始，j表示模式串匹配到了第j個位置。當樸素算法在主串第i個位置失配時，j會回到0，而i就+1，即從主串下一個位置繼續從模式串的第一個位置開始匹配，這樣會造成一種浪費——下一次匹配并沒有利用到之前失配的匹配的已經匹配好的信息。

而KMP算法對其進行了優化。

? KMP算法的原理

KMP算法認為“不需要將模式串一個位置一個位置地向右滑動”，例如：

當模式串"abca"在主串"abcd"失配后，我們沒有必要將i++，因為主串的下一個位置不是'a'，逐步滑動不一定會匹配。而KMP算法就會在發現失配后，直接將主串向右移動到可能匹配的最遠位置！

當模式串的某一個前綴是模式串的真子串時，我們在失配后可以直接將模式串移動到該位置。

（不知道怎么解釋了，看上面的3張圖片吧）

? Fail函數

為了實現主串失配時指針不回溯，只調整模式串指針j，使模式串向右盡可能遠地滑動，定義失配函數Fail(j)，表示當模式串中第j個字符與主串中Si失配時，在模式串中可能和主串中Si匹配的字符的位置。

轉移式則是：fail[i]=①-1(i=0);②max{ k|0<k<j, 且p₀ …p_k-1=p_j-k+1 …p_j-1 };③0(其他情況)。

?

---

?

? AC自動機

? 插入單詞和Trie樹是一樣的(￣▽￣)"

? 節點的結束單詞統計也和Trie樹是一樣的

? 獲取Fail函數

這里是用BFS獲取的。當單詞在字典樹的第二層就失配即在第一個字符就失配時，fail一定是0。也就是說第二層節點的fail都指向根節點。我們將第一層的所有節點都push進隊列里，然后如果節點u本來有"a"+i兒子v，則將v的fail指向u的fail的"a"+i兒子，否則直接將v指向u的fail的"a"+i兒子。

void GetFail(){queue< int > que;for(int i=0;i<26;i++) //遍歷第二層if(trie[0].son[i])trie[trie[0].son[i]].fail=0,que.push(trie[0].son[i]);while(!que.empty()){int u=que.front();que.pop();for(int i=0;i<26;i++) //找兒子節點if(trie[u].son[i]){ //有表示"a"+i的兒子trie[trie[u].son[i]].fail=trie[trie[u].fail].son[i];//指向父親的fail的"a"+i兒子que.push(trie[u].son[i]);}elsetrie[u].son[i]=trie[trie[u].fail].son[i];//直接將兒子指向父親fail的"a"+i兒子} }

? 主串上的遞推

設now是當前所處的節點。從根節點開始則now的初始值為0。從頭到尾枚舉主串字符str[i]，先將now賦值為now的str[i]兒子。再沿著now的fail指針一直回溯到根節點，可以實現遍歷str[0~i]的每一個后綴。對于str的每一個前綴都求出全部后綴，就相當于求出了str的全部子串。

根據題目要求統計答案。

?

void ACQuery(string str){int len=str.length();int now=0;for(int i=0;i<len;i++){now=trie[now].son[str[i]-'a']; //移動nowfor(int j=now;j;j=trie[j].fail) //按fail指針回溯ans[trie[j].ovr].num++; //統計答案} }

?

---

?

The End

Thanks for reading!

- Lucky_Glass

（Tab：如果我有沒講清楚的地方可以直接在郵箱lucky_glass@foxmail.com email我，在周末我會盡量解答并完善博客~）

轉載于:https://www.cnblogs.com/LuckyGlass-blog/p/9829574.html

總結

以上是生活随笔為你收集整理的【学时总结模板时间】◆学时·10 模板·3◆ AC自动机的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。