kmp算法如何在python項目中實現

這期內容當中小編將會給大家帶來有關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

上述就是小編為大家分享的kmp算法如何在python項目中實現了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。