kmp算法

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

比如

abababc

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

我們首先想到的最簡(jiǎn)單的辦法就是蠻力的一個(gè)字符一個(gè)字符的匹配，但那樣的時(shí)間復(fù)雜度會(huì)是O(m*n)

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

基本原理

舉個(gè)例子：

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

a與x不同，再次移動(dòng)

此時(shí)比較到了c與y，
于是下一步移動(dòng)成了下面這樣

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

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

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

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

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

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

移動(dòng)前

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

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

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

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

此時(shí)c與c相同，整個(gè)字符串自比對(duì)完成：

此時(shí)可能會(huì)沒有理解為什么匹配不成功的時(shí)候要再比對(duì)其前一位字符下的數(shù)字的位置，那是因?yàn)檫@是要找到前一個(gè)字符位置下的最長(zhǎng)相同前綴中的最長(zhǎng)相同前綴，就舉剛才的例子：

此時(shí)a前邊是abcab，所以要找到abcab的最長(zhǎng)相同前綴，就是ab，這時(shí)

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

時(shí)間復(fù)雜度

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

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

具體代碼

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

def same_start_end(s):
  """最長(zhǎng)前后綴相同的字符位數(shù)"""
  n = len(s) #整個(gè)字符串長(zhǎng)度
  j = 0 # 前綴匹配指向
  i = 1 # 后綴匹配指向
  result_list=[0]*n
  while i < n:
    if j == 0 and s[j] != s[i]: #　比較不相等并且此時(shí)比較的已經(jīng)是第一個(gè)字符了
      result_list[i] = 0  # 值為０
      i += 1 # 向后移動(dòng)
    elif s[j] != s[i] and j != 0: #比較不相等,將j值設(shè)置為ｊ前一位的result_list中的值，為了在之前匹配到的子串中找到最長(zhǎng)相同前后綴
      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是模式字符串，返回值為匹配到的第一個(gè)字符串的第一個(gè)字符的索引，沒匹配到返回-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]: # 對(duì)應(yīng)字符相同
      i += 1
      j += 1
      if j >= p_length: # 完全匹配
        return i-p_length
    elif s[i] != p[j]: # 不相同
      if j == 0:  # 與模式比較的是模式的第一個(gè)字符
        i += 1
      else:    # 取模式當(dāng)前字符之前最長(zhǎng)相同前后綴的前綴的后一個(gè)字符繼續(xù)比較
        j = next[j]
  if i == s_length:  # 沒有找到完全匹配的子串
    return -1

總結(jié)

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

最新評(píng)論