KMP字串尋找演算法

我們先假設有一字串 P ‘abababaaabc’ 。

另有一字串 S ‘aabca’,假設必須在 P 裡面找到S,我們會有以下步驟

  1. “‘a’bababaaabc” match “‘a’abc”
  2. “a’b’ababaaabc” match “a’a’bc”
  3. “ab’a’babaaabc” not match “aa’b’c”
  4. 關鍵:此時我們必須從第二個b開始找 “a’b’ababaaabc”。但這邊有一個問題,我已經遍尋過的,為什麼還需要再掃一次?

若使用此方法,則時間複雜度為O(P*S)

於是有了KMP演算法。方法如下,

  1. 我們先看S 也就是要用來匹配的短字串
  2. 你會發現 “‘a”a’bca” 一開始兩個a是一樣的
  3. 也就是說假設我今天比對前兩個都沒問題,那就代表我可以直接往後推一個,因為我第一個比對跟第二個比對是一樣的
  4. 我們可以將 S 一層一層拆解,並找出每一個的前綴跟後綴,藉此判斷當我們停在某一個項目時,可以快速找到已搜尋過的字母並跳過他

跟動態規劃的關係

再次重申動態規劃的兩個要點

  1. 分治法
  2. 當分治法分割出來的問題,一而再、再而三出現,就運用記憶法儲存這些問題的答案,避免重複求解(用空間換時間)

在KMP的理論中,我們每當遇到配對失敗的狀況,就必須依照相對應的數值跳轉答案。

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。