kmp算法

kmp算法用于字符串的模式匹配，也就是找到模式字符串在目標字符串的第一次出現(xiàn)的位置

比如

abababc

那么bab在其位置1處，bc在其位置5處

我們首先想到的最簡單的辦法就是蠻力的一個字符一個字符的匹配，但那樣的時間復雜度會是O(m*n)

kmp算法保證了時間復雜度為O(m+n)

基本原理

舉個例子：

發(fā)現(xiàn)x與c不同后，進行移動

a與x不同，再次移動

此時比較到了c與y，
于是下一步移動成了下面這樣

這一次的移動與前兩次的移動不同，之前每次比較到上面長字符串的字符位置后，直接把模式字符串的首字符與它對齊，這次并沒有，原因是這次移動之前，y與c對齊，但是y前邊的ab是與自己的前綴ab一樣，于是ab并不用再比較，直接從第三個位置開始比較，如圖：

所以說kmp算法對于這種情況就直接使用當前比較字符之前的最長相同的前后綴，然后將前綴與上面的長字符串對齊，繼續(xù)比

較后面的字符串。
這里kmp算法中的一個重要點就來了，如何找到模式字符串中每位字符之前的最長相同前后綴呢
這里繼續(xù)用一個例子舉例：

下面的數(shù)字記錄以該字符為結尾的最長前后綴相同子串的長度，先初始化為0,并且第一個字符下的數(shù)字確認為0
然后開始比較：

a與b不同，那么b下的數(shù)字也為0同理a與c不同，c下的數(shù)字也為0，接下來a與a對齊，如下

此時a與a相同，那么a下面的數(shù)字為1，也就是第二排字符串中當前比對的字符索引+1
接下來b與b相同，c與a不相同，那么此時上面的字符串不動，下面的字符串移動到當前比對位置即c的前一位的下方的數(shù)字的位置，如圖：

移動前

c的前一位是b，b下方的數(shù)字是0，所以將下面字符串的第0位與之前的比對位置對其，即：

當前比對位置如箭頭所示，然后繼續(xù)向后比較，一直比到c與a：

此時c與a不相同，那么比較下面字符的前一個字符的下方數(shù)字的位置，如圖

也就是位置為2的地方與上面比對位置對齊：

此時c與c相同，整個字符串自比對完成：

此時可能會沒有理解為什么匹配不成功的時候要再比對其前一位字符下的數(shù)字的位置，那是因為這是要找到前一個字符位置下的最長相同前綴中的最長相同前綴，就舉剛才的例子：

此時a前邊是abcab，所以要找到abcab的最長相同前綴，就是ab，這時

然后再移動到ab與ab對其的位置繼續(xù)比較即可

時間復雜度

簡單來講， 找到模式字符串中每位字符之前的最長相同前后綴的這個方法中，如果模式字符串的長度為m，那么上面的字符串的指向是一直向前移動的，下面字符串的整體也是一直向前移動的，最終移動的結果將會是長度為2m，所以比較次數(shù)也是最大為2m，時間復雜度為O(m)

kmp算法中，運用了找到模式字符串中每位字符之前的最長相同前后綴的這個方法的結果，然后使用類似的方法進行比較和移動，和上邊的解釋類似，如果這個要匹配的字符串長度為n，那最長的移動舉例也超不過2n，所以總的時間復雜度為O(m+n)

具體代碼

這里沒有進行傳入?yún)?shù)的驗證，使用時還要注意。

def same_start_end(s):
  """最長前后綴相同的字符位數(shù)"""
  n = len(s) #整個字符串長度
  j = 0 # 前綴匹配指向
  i = 1 # 后綴匹配指向
  result_list=[0]*n
  while i < n:
    if j == 0 and s[j] != s[i]: #　比較不相等并且此時比較的已經(jīng)是第一個字符了
      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]:  #相等則繼續(xù)比較
      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:    # 取模式當前字符之前最長相同前后綴的前綴的后一個字符繼續(xù)比較
        j = next[j]
  if i == s_length:  # 沒有找到完全匹配的子串
    return -1

總結

以上所述是小編給大家介紹的python實現(xiàn)kmp算法的實例代碼，希望對大家有所幫助，如果大家有任何疑問歡迎給我留言，小編會及時回復大家的！

最新評論