[TIL] 有關字串搜尋的演算法: KMP
TL;DR
KMP(Knuth–Morris–Pratt algorithm) 是字串搜尋的最佳化演算法，是由 MP Algorithm 優化而成，並且 KMP Algorithm 主要也只能解決某些問題 (要搜尋字串連鎖過多造成過多移動) ．
暴力法 -> MP (提供比對與快速移動的方式) -> KMP (提供連鎖的減少移動方式)
相關程式
如果需要可以執行的相關 MP KMP 程式，可以去拿這個 Go 的版本．
前言
紀錄一下關於 KMP 的學習紀錄，會講到 KMP(Knuth–Morris–Pratt algorithm) 主要就是因為一篇 DevOps 的求職文章．
所以決定去把它搞懂一下，順便寫一下相關程式．
注意 以下的部分由於我懶得畫圖，就沒有圖表介紹．如果要看圖表或是影片． 這一對教學影片很清楚． youtube: Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
原理
KMP(Knuth–Morris–Pratt algorithm) 本身是用來做字串搜尋的演算法．也就是有點類似 C 語言本身會提供的 strstr 也就是在一個字串裡面搜尋一個字串．
當然 KMP 跟 strstr 有些許的不同由於回傳的資料不同． KMP 回傳所有符合的索引位置，而 strstr只回傳第一個．
字串搜尋:
方便以下講解，字串 target 為我們的目標字串， want 就是我們想要找出的字串． 其中:
n = len(target)m = len(want)
暴力搜尋
解決問題:
講到在一個字串裡面要搜尋一個比較小的字串．比較直覺方式就是暴力法，也就是一個個比對．
方法論:
- 從字串
target的第i個位置開始找 (i從 0, 1, … n ) - 如果
target[i] == want[0]則繼續往下比對，一直比對到整串字串比對完畢． - 如果不成功，將指標移到
target[i+1]
// 1
// Target [ 1 2 3 4 7 4 5 6 7]
// Want [ 5 6 7
// 2
// Target [ 1 2 3 4 7 4 5 6 7]
// Want [ 5 6 7 ]
// 3
// Target [ 1 2 3 4 7 4 5 6 7]
// Want [ 5 6 7 ]
時間複雜度:
- 最差狀況:
O(m * n)
MP 演算法 (Morris–Pratt Algorithm)
解決問題:
使用暴力解法最大的問題是最差狀況的時間複雜度代價太高，需要想一些辦法減少比對的次數． 所以有人想到是不是搜尋過的地方可以直接跳到後面？
// 1
// Target [ 1 2 3 4 7 4 5 6 7]
// Want [ 5 6 7
// 2
// Target [ 1 2 3 4 7 4 5 6 7]
// Want [ 5 6 7 ]
這樣問題來了，如果你要搜尋的字串其實有某種程度是具有重複性的．比如說 [ 1 2 3 1 2 4] 可以看出來 1 2 是重複有兩組在裡面． 那麼在搜尋的時候就無法一次跳掉所有的 target ． 所以 MP 演算法提供以下的方式．
方法論:
- 先分析要找尋的字串 want ，所有重複出現的字串列出一個列表．成為 failure index
- want:
[A B C A B B D]-> failure function:[0 0 0 1 2 2 0]
- want:
- 開始搜尋，如果遇到不符合的字串． 尋找 want 前一個字元去尋找他的相對應的 failure index． 要往後移動的數字為:
已經比對的個數 - 前一個重複的位置- 假設比對到:
target: [ABCABCDDDD]
want: [ABCABBD]
^ 比對到第6個
//時候要移動的會是 5-2=3
target: [ABCABCDDDD]
want: [ ABCABBD]
留下的問題是，對於往後移動的計算方式．往往會因為後面一個跟移動後的第一個不搭配．要頻繁地移動．
時間複雜度:
- 最差狀況
O(m+n)
KMP 演算法 (Knuth–Morris-Pratt Algorithm)
原先MP演算法的問題
為了要解決移動後可能會遭遇的頻繁移動的問題，換句話說想要試著一次就把想要移動的部分到位． Knuth 在 failure function 上面增加了不少的判斷方式．
也就是試著在做 failed function 的時候，希望把之後可能會遇到的 failure function 移動兩次的狀態減少．
先來看看透過計算過後的 failure function 索引表．
0 1 2 3 4 5 6
string [A B C D A B D]
mpNext = [-1 0 0 0 0 1 2]
kmpNext = [-1 0 0 0 -1 0 2]
透過這個範例可以看到，當有不相同的字串發生在 5 的時候． 由於前面是A，你也會發現 4 5 的 AB 跟 0 1 的 AB一樣是連鎖的．
以下透過上面的例子來推導一次(先透過 MP 來推倒，查看原先容易出現的問題):
0 1 2 4 5 6
目標字串 [A B C A B D]
mpNext = [-1 0 0 0 1 2]
//1
搜尋字串 [A BCACCDDDAACABCDABD]
目標字串 [A BCABD]
^
//2
搜尋字串 [A B CDACCDDDAACABCDABD]
目標字串 [A B CDABD]
^
//3
搜尋字串 [AB C DACCDDDAACABCDABD]
目標字串 [AB C DABD]
^
//4
搜尋字串 [ABC D ACCDDDAACABCDABD]
目標字串 [ABC D ABD]
^
//5
搜尋字串 [ABCD A CCDDDAACABCDABD]
目標字串 [ABCD A BD]
^
//6
搜尋字串 [ABCDA C CDDDAACABCDABD]
目標字串 [ABCDA B D]
^
// 這時候發生不符合的狀態，根據 MP 的演算法
// 我們會移動到前面一個 A 的位址並且從 B 繼續開始比對
//7
搜尋字串 [ABCDA C CDDDAACABCDABD]
目標字串 [A B CDABD]
^
//由於 [0,1] AB 的連鎖跟 [4,5] AB 一樣，
//所以既然錯誤發生在[5] B，移動到前面的時候．
//接下來一定也會遇到 B ，就像現在．
//只好移動到最前面再比對一次
//8
搜尋字串 [ABCDA C CDDDAACABCDABD]
目標字串 [A BCDABD]
^
這就是問題所在， KMP 主要就要解決這種問題． 所以如果你只單單的移到 A 接下來往後的一定是 B 一定又會發生不同，而必須要在移動一次．
方法論:
簡單的原理條列如下，主要是修改在 failure function 索引表的數字:
- 如果發現前面有同樣的，先查看下一個是否跟前面的下一個是同樣． 如果是就在往前面一個相同的找． 簡單的說： 遇到連鎖，就再往前找．
- 如果不是”連鎖”，就可以單純的把前面的位址記錄下來．
以下拿上面的例子來做一次 kmpNext
目標字串 [ABCAB]
依照MP演算法，計算數字如下
目標字串 [A B C A B]
mpNex [-1 0 0 0 1]
但是由於找到第二個A的時候，發現第二個A的後面是B，而第一個A的後面也是B．於是就必須往前找． （往前找的動作，在程式碼裡面就是直接把前一個的 kmpNext 數值直接給後面．
目標字串 [A B C A B]
mpNext [-1 0 0 0 1]
kmpNex [-1 0 0 -1 0]
時間複雜度:
- 最差狀況
O(m+n)但是在某些狀況下，也就是你要尋找的字串如果具有相當多的連鎖． 比如說ABCABCAB或是AAABCDBCDBCD的狀態下就會變得比較快．
