###### tags: `pattern-matching`

# Aho-Corasick string matching
by Yoona

## intro

ㄝ都~ 進入這個演算法之前需要先去了解 "字典樹"、KMP 算法 這兩樣東西，那下面就是介紹 AC 算法的部分~

我們知道 KMP 算法是在一個長字串中搜索有無"一個"短字串的蹤跡，那如果同時給你多個短字串，需要你去"同時"比對，這個長字串中有無"這些短字串"的蹤跡時，我們就需要用到這個 AC 算法

這個概念對應到，有些網路攻擊是 string 的攻擊，若我們在資料庫中先存了一些可能攻擊網頁的 string 模板字串，並依照 AC 算法先把查找樹的架構架好，那在被外來 string 攻擊時，就可透過算法優化過的方式，用比較快的方式比對出是否為攻擊字串並抵禦，就可能可以免於同時間大量字串攻擊後網頁來不及防禦而破防的處境

---
## 算法解析
資料庫的短字串在左上，需比對的長字串在右上

示意圖如上~

1. 基本上就是依照字典樹的概念為短字串們架構出字典樹
這邊比較不一樣的地方是，和 KMP 一樣，我們要幫其連出字串比對出錯時，要回到已經比對完成的哪一步並繼續比對下去，以減少比對次數，那這邊是用 failure links 實現這個功能

* success : 匹配成功，繼續向可能的 child 走去
* failure : 這步匹配失敗，要回到先前的某一步
回到之前的某一步 : 最長後序對應的最長前序 ( 請見 KMP
* emit : 比對成功的部份就跟字典樹一樣，成功走到葉節點了
成功後的返回位和 failure link 一樣，如此可跳過已比對成功的前面部分

2. 好的，那目前就只要把 failure link 連接出來事情就大功告成了，但問題就是，要如何連出 failure link 哩?~
(線索 : KMP 的最長後序對應的最長前序)

那這邊就直接幫大家破梗拉~~ (撒花)
這邊會先講解步驟，後續會說明一些步驟的原因

根據 https://www.evanlin.com/about-aca/ 的詳細解說，將為大家整理出幾個重點 :
1. 架構順序是依照 BFS，至於為啥是因為 :
同一條樹枝上的 node ，比你淺層的 node 們的 failure link 要先架構好，你才能利用 parent node 已經幫你累積的前序紀錄
而這些 parent node 的 failure link 連接過程中，會需要現有的最多資源，因此同層或比他淺層的 node 們要先被架構出來，他才能利用現有的最大資源去連來連去

2. 建構時
* 如果該點的 parent 是 root，那該點 fail index 為 root

接著你會去查找你 parent 的 failure link 所連到的那個點，有沒有自己字母的 child
* 有的話，將 link 連到那個 child 上
* 沒的話，返回 root 去看有無自己字母的 child，有的話 link 去該 root 的 child，沒的話，就停留在 root

至於為什麼是這樣建構的話，就是充分利用 parent node 留給你的 最長後序對應的最長前序 這件事情拉~

3. 另外，一個字串存取完畢後記得將該節點標記起來，往後查找時若順利走到該點，則代表命中一個字串了

---
小結尾

．架構的 code 部分我還不確定是用 class 令出 node 還是用 array 存 tree，class 的話 link 的實現可用 pointer，array 的話則是記住 link 去的 node 的 index

那講到這邊應該是結束了XD