在看子串匹配問題的時候，書上的關于KMP的算法的介紹總是理解不了。看了一遍代碼總是很快的忘掉，后來決定好好分解一下KMP算法，算是給自己加深印象。

在將KMP字串匹配問題的時候，我們先來回顧一下字串匹配的暴力解法：

假設字符串str為: "abcgbabcdh",  字串substr為: "abcd"

 從第一個字符開始比較，顯然兩個字符串的第一個字符相等（'a'=='a'）,然后比較第二個字符也相等（'b'=='b'）,繼續(xù)下去，我們發(fā)現(xiàn)第4個字符不相等了（'g'!='d'）,這時候我們讓'g'和字串的開頭'a'比較，若兩者相同，則同時后移一位比較下一個字母，不同則將str中比較的字符后移一位，然后和字串中開始的'a'比較。以此類推....我們可以在str中找到substr字串，并返回字串的位置。

這種暴力搜索方法很顯然時間復雜度是O(m*n) n,m分別表示str字符串和substr字串的長度。m*n的復雜度顯然是比較大的，當m或者n很大的時候，時間開銷會很大。KMP算法則可以將時間復雜度下降到O(m+n),和O(m*n)相比明顯下降。

KMP算法和暴力搜索方法之間的差別在于KMP算法在出現(xiàn)字符串不相等的情況時，不需要返回到字串的開頭重新比較。

如何保證字符串不相等的情況出現(xiàn)時，字串不從最開始開始比較呢，這時候臨時數(shù)組就登場了。

書本上總是介紹說是，判斷此時字串中是否有相同前綴和后綴，懵逼臉......

看完臨時數(shù)組是如何構造的你應該差不多就知道前后綴問題了。

** 臨時數(shù)組 ** ： 我們假設子串為 'abcabg', 開始時j指向第一個字符，i指向第二個字符(j=0, i=1)。并且令pnext[0] = 0,如下圖所示：

1)  由于substr[j] != substr[i] 并且j=0, 令pnext[i] = 0 , i往后移一位。(步驟1后，j=0， i=2)

2)  由于substr[j] != substr[i] 并且j=0, 令pnext[i] = 0 , i往后移一位。(步驟2后，j=0， i=3)

3)  此時substr[j] == substr[i], 令pnext[i] = j + 1, 并且 i , j 都后移一位。(步驟3后，j=1，i=4)

這時候我們來看一下臨時數(shù)組的狀態(tài)：

4)  substr[j] == substr[i] 還是成立, 令pnext[i] = j+1,  并且i, j都后移一位。(j=2,  i=5)

5)  此時 substr[j] != substr[i]，由于j=2(不為0)，令j = pnext[j-1]  (由于pnext[j-1] = pnext[1] = 0 ==> j=0, 保持 i=5)

6)  substr[j] != substr[i], 并且j=0, 令pnext[i] = 0, 并使i后移一位。(j=0， i=6)

7)  substr[j] == substr[i],  同理pnext[i] = j+1 ,并且i, j都向后移動一位。(j=1， i=7)

8)  substr[j] != substr[i], j != 0, j = pnext[j-1] = pnext[0] = 0。 (j=0, i=7)

9)  substr[j] != substr[i], 且j=0, 令pnext[i] = 0。(此時i到達最后一個位置，并且pnext數(shù)組全部賦值完畢。pnext數(shù)組構造結束)

臨時數(shù)組構造完畢之后，就可以使用 KMP算法 了。

還是假設 字符串str = 'abgabcabgacyf', 子串 substr = 'abcabgac'.

令i指向str的第一個字符，j指向substr第一個字符。KMP算法的詳細運行步驟如下：

<1> str[i] == substr[j], i = i+1,  j = j+1. (步驟1之后: i=1, j=1)

<2> str[i] == substr[j], i = i+1, j = j+1. (i=2, j=2)

<3> str[i] != substr[j], 此時j != 0, 所以臨時數(shù)組pnext就派上用場了。令 j = pnext[j-1].  （i=2,  j = pnext[2-1] = 0）

如果存在前后綴的話(即pnext[j-1]!=0)，由于此步驟之前的substr與str相同(要不然 j 也不會往后移動了)，這里舉一個例子幫助理解：

如圖，當i和j位于圖中時刻，字符j與p不相等。(p之前的abcdab肯定和上面相等，要不然j不會移動到字符p上)，按照暴力搜索的方法是不是要讓j和子串的第一個字符a比較呢。KMP算法就不需要，我們可以看到子串中p之前的字符存在最大相等前后綴為'ab', 那在下一次比較的時候‘a(chǎn)b'是不是就不用比較了呢。從而直接比較j和c呢？？(如下圖)這就是KMP算法的精髓所在。

<4> 這時候str[i] != substr[j], 但是和步驟<3>不一樣的是，此時j=0（由于pnext[-1]不存在，j不能等于pnext[j-1]了）。所以子串開頭只能和str中下一個字符比較，即i = i+1。（i=3, j=0）

<5> str[i] == substr[j] ==> i = i+1, j = j+1. (i=4, j=1)

<6> 以此類推。這一過程存在兩種方法中止，即i或者j不能再加1(加1就會發(fā)生越界的時候)。假設str的長度為n，substr的長度為m。當j==m時，說明找到了子串，否則沒有找到。

def KMP_algorithm(string, substring):
  '''
  KMP字符串匹配的主函數(shù)
  若存在字串返回字串在字符串中開始的位置下標，或者返回-1
  '''
  pnext = gen_pnext(substring)
  n = len(string)
  m = len(substring)
  i, j = 0, 0
  while (i<n) and (j<m):
    if (string[i]==substring[j]):
      i += 1
      j += 1
    elif (j!=0):
      j = pnext[j-1]
    else:
      i += 1
  if (j == m):
    return i-j
  else:
    return -1
def gen_pnext(substring):
  """
  構造臨時數(shù)組pnext
  """
  index, m = 0, len(substring)
  pnext = [0]*m
  i = 1
  while i < m:
    if (substring[i] == substring[index]):
      pnext[i] = index + 1
      index += 1
      i += 1
    elif (index!=0):
      index = pnext[index-1]
    else:
      pnext[i] = 0
      i += 1
  return pnext
if __name__ == "__main__":
  string = 'abcxabcdabcdabcy'
  substring = 'abcdabcy'
  out = KMP_algorithm(string, substring)
  print(out)

 代碼結果返回子串開始時的坐標位置。

看到這里如果還是沒有懂得話，那就說明我表述的還不夠好，推薦看看視頻。

快速傳送門：戳我

總結

以上所述是小編給大家介紹的詳解小白之KMP算法及python實現(xiàn)，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！

最新評論