###### tags: `Text`
# String Searching
:::info
「字串搜尋」。在兩個字串T(Text)和P(Pattern)中，找出T當中是否有一段字串正好是P，並找出位置。
暴力法 -> MP (提供比對與快速移動的方式) -> KMP (提供連鎖下的減少移動方式)
:::
## 窮舉法
移動P，對準T的各個位置逐一比對字元來判斷是否相等。時間複雜度為<font color=red>O(TP)</font>。

## Morris-Pratt Algorithm (MP)
如果我們預先知道abzab的「次長的相同前綴後綴」是ab，
就可以一口氣大幅移動P，也就減少搜尋次數
### failure function
預先計算P的每一個前綴的「次長的相同前綴後綴」，以備不時之需！failure function是一個字串函數：輸入字串的其中一個前綴，則輸出該前綴的「次長的相同前綴後綴」。
### 字串搜尋
1. 預先計算P的每種前綴的「次長的相同前綴後綴」，O( P )。
2. 從左往右進行字串搜尋，依序比對字元，O(T)。
* 當比對成功即遇到相同字元：繼續比對下個字元。
* 當比對失敗即遇到相異字元：從比對成功的字串片段，取其「次長的相同前綴後綴」來大幅移動P。
* 當全部比對成功即搜尋到P：從比對成功的P，取其「次長的相同前綴後綴」來大幅移動P。
3. <font color=red>總時間複雜度為 O(T + P)</font>

## Knuth-Morris-Pratt Algorithm (KMP)
Morris-Pratt Algorithm 當中，當比對到上圖之處， c != b ，所以需要向右挪動 P 。找到 abca 的「次長的相同前綴後綴」，也就是 a 。然後向右挪動 P ，最後左端凸出一段 a ，如下圖所示。
接下來就繼續比對字元。在這裡 c != b ，所以又要挪動 P 了。

Knuth 則是多想了一步：連續挪動 P ，能不能預先偵測呢？ Knuth 發現，找到 abca 的「次長的相同前綴後綴」 a 之後，看看 a 的下一個字元（是 b ），是否仍是 abca 的下一個字元（也是 b ）。如果兩個字元一樣的話，那就表示 P 鐵定會連續挪動兩次，兩次比較都是 c != b 。

既然鐵定會挪動兩次，那乾脆直接移到定位不就好了？於是 Knuth 在計算 failure function 的時候，就額外加了一個判斷：找到 abca 的相同前綴後綴 f(abca) = a 之後，如果 f(abca) 的下一個字元恰巧仍是 abca 的下一個字元，那麼就令 f(abca) = f(a) ，也就是再多找一次 a 的相同前綴後綴。如此一來， P 只要移一次就行了。

由於是用遞迴定義 failure function ，所以連續挪動三次、四次、五次的情況，經過遞迴計算，最後都會變成一次移到定位。

## Trie (字典樹)
字典樹(Trie)，也被稱為單詞搜尋樹，是一種很特別的樹狀資料結構，如同其名，它就像一本字典，可以讓你快速的依照字母插入、尋找字串，由於高效的特性，特別適用於大量字串出現的時候。

### 特性
利用每個字的共同前綴(common prefix)當儲存依據，並以此來節省儲存空間以及加速搜尋時間，並以此來節省儲存空間以及加速搜尋時間。

以樹狀結構儲存，其每個節點代表一個字母，但根節點不能包含任何字母。每個子節點分別代表字串的下一個字母，而整棵樹的高度為最長字串的長度+1。

查詢字典樹時會從根節點向下搜尋，利用指標方式來記錄字串的轉換狀態用來加速搜尋時間。

### 範例
與二元搜尋樹不同，鍵不是直接儲存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首，也就是這個節點對應的字串，而根節點對應空字串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。

在圖示中，鍵標註在節點中，值標註在節點之下。每一個完整的英文單詞對應一個特定的整數。鍵不需要被顯式地儲存在節點中。圖示中標註出完整的單詞，只是為了演示trie的原理。

[Trie演算法視覺化](https://www.cs.usfca.edu/~galles/visualization/Trie.html)
## 參考
* [字串搜尋](http://www.csie.ntnu.edu.tw/~u91029/StringSearching.html#1)
* [字典樹、線段樹、樹狀數組](http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d)