字元串比對算法(三)-KMP算法

今天我們來聊一下字元串比對算法裡最著名的算法-KMP算法，KMP算法的全稱是 Knuth Morris Pratt 算法，是根據三位作者（D.E.Knuth，J.H.Morris 和 V.R.Pratt）的名字來命名的。

KMP算法原理

      KMP的算法核心思想是，當模式串b和主串a在進行比對的時候，如果遇到不比對的字元，我們希望找到一種規律，可以使得模式串b多向後滑動幾位，跳過那些肯定不比對的情況。

      首先我們先明确二個定義：在模式串和主串比對的過程中，我們把不能比對的字元叫做壞字元，把已經比對的那段字元叫做好字首。在模式串和主串比對的過程中，當遇到壞字元後，對于已經比對過的好字首，能否找到一種規律，将模式串可以滑動多位呢。

      其實我們隻需要拿好字首本身，在他的字尾子串中，查找最長的那個可以跟好字首的字首子串比對的。假設最長可比對的那部分字首子串是{u}，長度是k。我們可以把模式串一次性先後滑動j-k位，即當比對到壞字元時，我們把j更新為k，然後i不變，然後再繼續比對。

     下面我們再明确兩個定義，我們把好字首的所有字尾子串中，最長的可以比對字首子串的那個字尾稱為最長可比對字尾子串，對應的字首子串叫做最長可比對字首子串。那如何來求好字首的最長可比對字首和字尾子串呢？

       KMP算法是通過建構了一個數組來求的。該數組的下标是每個字首結尾字元下标，該數組的值是這個字首的最長可以比對字首子串的結尾字元下标。我們把這個數組定義為 next 數組，同時也可以稱為是失效函數。如下圖所示。

next數組的計算方法

    我們來思考這麼一個問題。如果next[i-1]=k-1，也就是說子串b[0, k-1]是b[0, i-1]的最長可比對字首子串。如果子串 b[0, k-1]的下一個字元 b[k]，與 b[0, i-1]的下一個字元 b[i]比對，那麼子串 b[0, k]就是 b[0, i]的最長可比對字首子串。是以，next[i]等于 k。如果 b[0, k-1]的下一字元 b[k]跟 b[0, i-1]的下一個字元 b[i]不相等呢？那我們這個時候就不能簡單地通過 next[i-1]得到 next[i]了。這個時候該怎麼辦呢？我們假設 b[0, i]的最長可比對字尾子串是 b[r, i]。如果我們把最後一個字元去掉，那 b[r, i-1]肯定是 b[0, i-1]的可比對字尾子串，但不一定是最長可比對字尾子串。是以，既然 b[0, i-1]最長可比對字尾子串對應的模式串的字首子串的下一個字元并不等于 b[i]，那麼我們就可以考察 b[0, i-1]的次長可比對字尾子串 b[x, i-1]對應的可比對字首子串 b[0, i-1-x]的下一個字元 b[i-x]是否等于 b[i]。如果等于，那 b[x, i]就是 b[0, i]的最長可比對字尾子串。可是，如何求得 b[0, i-1]的次長可比對字尾子串呢？次長可比對字尾子串肯定被包含在最長可比對字尾子串中，而最長可比對字尾子串又對應最長可比對字首子串 b[0, y]。于是，查找 b[0, i-1]的次長可比對字尾子串，這個問題就變成，查找 b[0, y]的最長比對字尾子串的問題了。按照這個思路，我們可以考察完所有的 b[0, i-1]的可比對字尾子串 b[y, i-1]，直到找到一個可比對的字尾子串，它對應的字首子串的下一個字元等于 b[i]，那這個 b[y, i]就是 b[0, i]的最長可比對字尾子串。這塊比較繞，可以先看代碼，然後反過來多讀幾遍。

#b表示模式串
#m表示模式串的長度
def getNext(b,m):
     next=[-1]*m
     k=-1
     for i in range(1,m):
          while k!=-1 and b[k+1]!=b[i]:
               k=next[k]
          if b[k+1]==b[i]:
               k=k+1
​
          next[i]=k
     return next
      

　　

 我們有了next數組後，就可以動手來實作kmp算法了。

#b表示模式串
#m表示模式串的長度
def getNext(b,m):
     next=[-1]*m
     k=-1
     for i in range(1,m):
          while k!=-1 and b[k+1]!=b[i]:
               k=next[k]
          if b[k+1]==b[i]:
               k=k+1

          next[i]=k
     return next

def kmp(a,n,b,m):
     next=getNext(b,m)
     print(next)
     j=0
     for i in range(n):
          while j>0 and a[i]!=b[j]:
               j=next[j-1]+1

          if(a[i]==b[j]):
               j=j+1

          #找到比對模式串的了
          if(j==m):
               return i-m+1

     return -1