在看子串匹配問題的時(shí)候，書上的關(guān)于KMP的算法的介紹總是理解不了?？戳艘槐榇a總是很快的忘掉，后來決定好好分解一下KMP算法，算是給自己加深印象。

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

假設(shè)字符串str為: "abcgbabcdh",  字串substr為: "abcd"

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

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

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

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

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

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

** 臨時(shí)數(shù)組 ** ： 我們假設(shè)子串為 'abcabg', 開始時(shí)j指向第一個(gè)字符，i指向第二個(gè)字符(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)  此時(shí)substr[j] == substr[i], 令pnext[i] = j + 1, 并且 i , j 都后移一位。(步驟3后，j=1，i=4)

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

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

5)  此時(shí) 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都向后移動(dòng)一位。(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。(此時(shí)i到達(dá)最后一個(gè)位置，并且pnext數(shù)組全部賦值完畢。pnext數(shù)組構(gòu)造結(jié)束)

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

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

令i指向str的第一個(gè)字符，j指向substr第一個(gè)字符。KMP算法的詳細(xì)運(yùn)行步驟如下：

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

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

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

<4> 這時(shí)候str[i] != substr[j], 但是和步驟<3>不一樣的是，此時(shí)j=0（由于pnext[-1]不存在，j不能等于pnext[j-1]了）。所以子串開頭只能和str中下一個(gè)字符比較，即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就會(huì)發(fā)生越界的時(shí)候)。假設(shè)str的長度為n，substr的長度為m。當(dāng)j==m時(shí)，說明找到了子串，否則沒有找到。

def KMP_algorithm(string, substring):
  '''
  KMP字符串匹配的主函數(shù)
  若存在字串返回字串在字符串中開始的位置下標(biāo)，或者返回-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):
  """
  構(gòu)造臨時(shí)數(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)

 代碼結(jié)果返回子串開始時(shí)的坐標(biāo)位置。

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

快速傳送門：戳我

總結(jié)

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

最新評論