我們先假設有一字串 P ‘abababaaabc’ 。
另有一字串 S ‘aabca’，假設必須在 P 裡面找到S，我們會有以下步驟
- “‘a’bababaaabc” match “‘a’abc”
- “a’b’ababaaabc” match “a’a’bc”
- “ab’a’babaaabc” not match “aa’b’c”
- 關鍵：此時我們必須從第二個b開始找 “a’b’ababaaabc”。但這邊有一個問題，我已經遍尋過的，為什麼還需要再掃一次？
若使用此方法，則時間複雜度為O(P*S)
於是有了KMP演算法。方法如下，
- 我們先看S 也就是要用來匹配的短字串
- 你會發現 “‘a”a’bca” 一開始兩個a是一樣的
- 也就是說假設我今天比對前兩個都沒問題，那就代表我可以直接往後推一個，因為我第一個比對跟第二個比對是一樣的
- 我們可以將 S 一層一層拆解，並找出每一個的前綴跟後綴，藉此判斷當我們停在某一個項目時，可以快速找到已搜尋過的字母並跳過他
跟動態規劃的關係
再次重申動態規劃的兩個要點
- 分治法
- 當分治法分割出來的問題，一而再、再而三出現，就運用記憶法儲存這些問題的答案，避免重複求解(用空間換時間)
在KMP的理論中，我們每當遇到配對失敗的狀況，就必須依照相對應的數值跳轉答案。