kmp演算法python實現
- 2020 年 1 月 16 日
- 筆記
kmp演算法python實現
kmp演算法
kmp演算法用於字元串的模式匹配，也就是找到模式字元串在目標字元串的第一次出現的位置 比如 abababc 那麼bab在其位置1處，bc在其位置5處 我們首先想到的最簡單的辦法就是蠻力的一個字元一個字元的匹配，但那樣的時間複雜度會是O(m*n) kmp演算法保證了時間複雜度為O(m+n)
基本原理
舉個例子：
發現x與c不同後，進行移動
a與x不同，再次移動
此時比較到了c與y， 於是下一步移動成了下面這樣
這一次的移動與前兩次的移動不同，之前每次比較到上面長字元串的字元位置後，直接把模式字元串的首字元與它對齊，這次並沒有，原因是這次移動之前，y與c對齊，但是y前邊的ab是與自己的前綴ab一樣，於是ab並不用再比較，直接從第三個位置開始比較，如圖：
所以說kmp演算法對於這種情況就直接使用當前比較字元之前的最長相同的前後綴，然後將前綴與上面的長字元串對齊，繼續比較後面的字元串。 這裡kmp演算法中的一個重要點就來了，如何找到模式字元串中每位字元之前的最長相同前後綴呢 這裡繼續用一個例子舉例：
下面的數字記錄以該字元為結尾的最長前後綴相同子串的長度，先初始化為0,並且第一個字元下的數字確認為0 然後開始比較：
a與b不同，那麼b下的數字也為0同理a與c不同，c下的數字也為0，接下來a與a對齊，如下
此時a與a相同，那麼a下面的數字為1，也就是第二排字元串中當前比對的字元索引+1 接下來b與b相同，c與a不相同，那麼此時上面的字元串不動，下面的字元串移動到當前比對位置即c的前一位的下方的數字的位置，如圖： 移動前
c的前一位是b，b下方的數字是0，所以將下面字元串的第0位與之前的比對位置對其，即：
當前比對位置如箭頭所示，然後繼續向後比較，一直比到c與a：
此時c與a不相同，那麼比較下面字元的前一個字元的下方數字的位置，如圖
也就是位置為2的地方與上面比對位置對齊：
此時c與c相同，整個字元串自比對完成：
此時可能會沒有理解為什麼匹配不成功的時候要再比對其前一位字元下的數字的位置，那是因為這是要找到前一個字元位置下的最長相同前綴中的最長相同前綴，就舉剛才的例子：
此時a前邊是abcab，所以要找到abcab的最長相同前綴，就是ab，這時
然後再移動到ab與ab對其的位置繼續比較即可
時間複雜度
簡單來講， 找到模式字元串中每位字元之前的最長相同前後綴的這個方法中，如果模式字元串的長度為m，那麼上面的字元串的指向是一直向前移動的，下面字元串的整體也是一直向前移動的，最終移動的結果將會是長度為2m，所以比較次數也是最大為2m，時間複雜度為O(m) kmp演算法中，運用了找到模式字元串中每位字元之前的最長相同前後綴的這個方法的結果，然後使用類似的方法進行比較和移動，和上邊的解釋類似，如果這個要匹配的字元串長度為n，那最長的移動舉例也超不過2n，所以總的時間複雜度為O(m+n)
具體程式碼
這裡沒有進行傳入參數的驗證，使用時還要注意。
def same_start_end(s): """最長前後綴相同的字元位數""" n = len(s) #整個字元串長度 j = 0 # 前綴匹配指向 i = 1 # 後綴匹配指向 result_list=[0]*n while i < n: if j == 0 and s[j] != s[i]: # 比較不相等並且此時比較的已經是第一個字元了 result_list[i] = 0 # 值為０ i += 1 # 向後移動 elif s[j] != s[i] and j != 0: #比較不相等,將j值設置為ｊ前一位的result_list中的值，為了在之前匹配到的子串中找到最長相同前後綴 j = result_list[j-1] elif s[j] == s[i]: #相等則繼續比較 result_list[i] = j+1 j = j+1 i = i+1 return result_list
def kmp(s,p): """kmp演算法,s是字元串，p是模式字元串，返回值為匹配到的第一個字元串的第一個字元的索引，沒匹配到返回-1""" s_length = len(s) p_length = len(p) i = 0 # 指向s j = 0 # 指向p next = same_start_end(p) while i < s_length: if s[i] == p[j]: # 對應字元相同 i += 1 j += 1 if j >= p_length: # 完全匹配 return i-p_length elif s[i] != p[j]: # 不相同 if j == 0: # 與模式比較的是模式的第一個字元 i += 1 else: # 取模式當前字元之前最長相同前後綴的前綴的後一個字元繼續比較 j = next[j] if i == s_length: # 沒有找到完全匹配的子串 return -1
