Learning Objectives
- 寫出暴力比對，說明最壞情況要比較約 n × m 次
- 算出一個字串的失敗函數（lps 陣列），說明它記錄的是「最長的相同前綴與後綴」
- 追蹤 KMP 比對：失配時文字的位置不回頭，只把模式往右滑
- 說明 Rabin-Karp 的滾動雜湊怎麼在 O(1) 內算出下一個視窗的雜湊值，以及為什麼雜湊值相同還要逐字確認
- 使用 Python、C++、Java 內建的字串搜尋函式
在一段文字裡找一個字串
在文件裡按 Ctrl + F 找一個詞、在 DNA 序列裡找一段基因、在記錄檔裡找錯誤訊息：這些都是字串比對（string matching）。 給一段文字（text，長度 n）和一個模式（pattern，長度 m），找出模式在文字裡出現的所有位置。
這一課的範例都用同一組資料：
text = ABABDABACDABABCABAB （n = 19）
pat = ABABCABAB （m = 9）
答案是索引 10。我們會用三種方法找它，數一數各自比較了幾次字元：
| 方法 | 想法 | 最壞情況 |
|---|---|---|
| 暴力比對 | 模式對齊每個位置，一個字元一個字元比 | O(n × m) |
| KMP | 失配時利用已經比對過的資訊，文字不回頭 | O(n + m) |
| Rabin-Karp | 先比雜湊值，相同才逐字確認 | 平均 O(n + m)，最壞 O(n × m) |
暴力比對：每個位置都從頭比
把模式的開頭對齊 text[i]，從 j = 0 開始一個字元一個字元比；遇到不一樣就放棄這個位置，i 加 1、j 回到 0 重新比。注意 i = 0 時已經比對上 ABAB 四個字元，失配後下一輪卻從 i = 1 從頭比起，前面得到的資訊全部丟掉了。
暴力比對的最壞情況
範例只比了 29 次，因為大部分位置第一、二個字元就不一樣了。但遇到下面這種文字，每個位置都要比到模式的最後一個字元才失配：
text = AAAAAAAAAAAAAAAAAAAA （20 個 A）
pat = AAAAB
16 個位置、每個位置比 5 次，共 80 次。一般來說有 n - m + 1 個位置、每個最多比 m 次，最壞是 O(n × m)。 文字有 10 萬個字元、模式有 100 個字元時，最壞要比約 1,000 萬次。
問題出在：失配時，我們其實已經知道文字裡剛剛比過的那幾個字元是什麼（它們和模式的前幾個字元相同），暴力比對卻把這些資訊丟掉、讓文字的位置倒退回去重比。 KMP 演算法由 Knuth、Morris、Pratt 在 1977 年發表，它的想法就是不讓文字的位置倒退。
KMP 的準備：失敗函數
假設模式 ABABCABAB 已經和文字對上了前 4 個字元 ABAB，第 5 個字元失配。已經對上的 ABAB 裡，
結尾的 AB 剛好也是開頭的 AB。所以不必從頭比，可以直接把模式往右滑，讓模式開頭的 AB 對齊文字裡剛才結尾的 AB，從模式的第 2 個字元繼續比。
要滑多少，只和模式本身有關，可以事先算好。這張表叫失敗函數（failure function），常寫成 lps 陣列（longest proper prefix which is also suffix）：
lps[i]＝pat[0..i]這一段裡，「既是前綴、又是後綴」的最長長度（不能是整段本身）
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| pat[i] | A | B | A | B | C | A | B | A | B |
| lps[i] | 0 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 |
例如 lps[3] = 2：ABAB 的前綴 AB 和後綴 AB 相同。lps[8] = 4：ABABCABAB 的前綴 ABAB 和後綴 ABAB 相同。
計算 lps 時，用 k 記住「目前相同前後綴的長度」：下一個字元 pat[i] 接得上 pat[k]，長度就加 1；接不上，就退回 lps[k - 1]（次長的相同前後綴）再試。
算出 lps 陣列
前面 ABAB 一路接得上，k 長到 2。到了 i = 4 的 C：pat[4] 和 pat[2] 不同，k 退到 lps[1] = 0，再和 pat[0] 比也不同，所以 lps[4] = 0。之後的 ABAB 又從頭接起來，最後 lps[8] = 4。
想一想：暴力比對與 lps
用暴力比對在 AAAAAAAAAA（10 個 A）裡找 AAAB，總共比較幾次字元？
模式 ABAB 的 lps 陣列是什麼？
暴力比對最壞情況比較慢，主要原因是什麼？
KMP 比對：文字不回頭
有了 lps，比對時用 i 走文字、j 記住「模式已經對上幾個字元」：
text[i]和pat[j]相同：j加 1- 不同而且
j > 0：把j改成lps[j - 1]（模式往右滑，保留已經對上的前綴），i不動，再比一次 - 不同而且
j == 0：模式開頭就對不上，i往前走 j == m：找到了，起點是i - m + 1；再把j改成lps[j - 1]繼續找下一個
i 從頭到尾只往前走 n 次；j 每次往回退，退的總量不會超過它前進的總量，所以比對最多約 2n 次，加上算 lps 的 O(m)，整體是 O(n + m)。
KMP：失配時模式往右滑
前面幾步先算 lps（和上一個範例相同）。比對時注意 i = 4：已經對上 ABAB（j = 4），D 和 C 不同，j 退成 lps[3] = 2，起點從 0 跳到 2，i 留在 4 沒有回頭。整段比對共比較 23 次，暴力比對是 29 次；換成上面「20 個 A 找 AAAAB」的例子，暴力比對 80 次，KMP 只要 36 次。
Rabin-Karp：先比雜湊值
另一種想法來自 Karp 與 Rabin 在 1987 年發表的演算法：把每個長度 m 的視窗算成一個數字（雜湊值，第 12 課）， 先比數字，數字相同才逐字確認。比一個數字只要一次，比字串要 m 次。
關鍵是滾動雜湊（rolling hash）：把字串看成 B 進位的數字，再取除以 M 的餘數。視窗往右移一格時，不必重算整段：
h = (h - 最左邊的數字 * p % M + M) % M # 去掉最左邊那一位（p＝B 的 m-1 次方除以 M 的餘數）
h = (h * B + 右邊新的數字) % M # 左移一位、接上新的一位
範例用經典的十進位例子：B = 10、M = 13，模式 31415 的雜湊值是 31415 除以 13 的餘數 7。
為什麼要寫成 (h - x * p % M + M) % M？ 減法可能得到負數。Python 的 % 對負數會回傳正的餘數，
C++ 與 Java 卻會回傳負數（例如 -3 % 13 在 Python 是 10，在 C++、Java 是 -3）。先加上 M 再取餘數，三種語言的結果就一致。
溢位：實際使用時 M 會取很大的質數（例如 1,000,000,007），h * B 可能超過 int 的上限（約 21 億），
所以 C++ 用 long long、Java 用 long。範例的 M 很小，寫成 long long／long 是為了養成習慣。
Rabin-Karp：滾動雜湊與偽命中
每移一格，h 只用兩行就更新好。索引 6 的視窗 31415 雜湊值是 7，逐字確認相同，找到了。索引 12 的視窗 67399 雜湊值也是 7（67399 除以 13 也餘 7），但字串不同，這叫偽命中（spurious hit）：雜湊值相同不代表字串相同，所以一定要逐字確認。
各語言內建的字串搜尋
實際寫程式時，直接用語言內建的函式就好，它們都經過最佳化：
| 語言 | 寫法 | 找不到時 |
|---|---|---|
| Python | text.find(pat)：第一次出現的索引 |
-1 |
| Python | pat in text：有沒有出現 |
False |
| C++ | text.find(pat)：第一次出現的索引；text.find(pat, pos) 從 pos 開始找 |
string::npos |
| Java | text.indexOf(pat)；text.indexOf(pat, from) 從 from 開始找 |
-1 |
| Java | text.contains(pat) |
false |
要找出所有出現位置，就把上一次找到的位置加 1 當作下一次的起點，一直找到回傳 -1（或 npos）為止。
pos = text.find(pat)
while pos != -1:
print(pos)
pos = text.find(pat, pos + 1)
自己實作 KMP、Rabin-Karp 的場合，通常是內建函式做不到的變化：一次找很多個模式、在二維的圖片裡找圖樣（Rabin-Karp 的雜湊可以推廣到二維）、 比較很多段文字有沒有重複內容（抄襲比對常用滾動雜湊）。另一個常見的演算法是 Boyer–Moore，從模式的最後一個字元往前比，實務上常常可以一次跳過好幾個字元。
想一想：KMP 與 Rabin-Karp
B = 10、M = 13，視窗 31415 的雜湊值是 7，p = 10⁴ 除以 13 的餘數 = 3。視窗右移一格變成 14152，新的雜湊值是多少？
KMP 已經對上模式的前 j 個字元，下一個字元失配（j > 0）時會怎麼做？
Rabin-Karp 在雜湊值相同時為什麼還要逐字比對？
實作：算出幾個模式的 lps
完成 build_lps，回傳模式的 lps 陣列。程式會印出四個模式的結果。AABAACAABAA 的第 5 個字元 C 會讓 k 連退兩次，是檢查「退回」寫得對不對的好例子。
重點整理
- 暴力比對：模式對齊每個位置從頭比，最壞 O(n × m)；失配時把已經比對過的資訊丟掉
- lps（失敗函數）：
lps[i]是pat[0..i]最長的相同前後綴長度，只和模式有關，O(m) 算好 - KMP：失配時
j = lps[j - 1]、i不回頭，整體 O(n + m) - Rabin-Karp：滾動雜湊在 O(1) 內算出下一個視窗的雜湊值；雜湊值相同還要逐字確認（偽命中）
- 取餘數時寫
(h - x * p % M + M) % M，三種語言對負數的處理才會一致；C++／Java 用long long／long避免溢位 - 日常使用內建的
find／indexOf；需要多模式、二維或大量重複比對時，才自己實作
下一課：P、NP 與難解問題。回溯法遇到 n! 或 2ⁿ 的成長時，是不是一定有更好的方法？這是電腦科學裡最有名、至今沒有解決的問題之一。