字元串的模式比對算法（思想+python實作）

樸素的模式比對算法

一個例子：

從主串 S = "goodjob"中，找到子串 T = "job"的位置。我們通常需要下面的步驟。

1. 将子串"job"與主串S從第一位對應比對。即判斷 whether 'g' == 'j';
2. 判斷結果為否，繼續比對 whether 'o' == 'j';
3. 直到找到第一位比對 'j' = 'j';
4. 繼續比對完整 S[4:7] == 'job' == T。
           

是一種最簡單的比對算法，暴力易實作，但有許多備援的步驟。

KMP 模式比對算法

總的思想是：通過字元串已有的資訊來規避樸素模式比對中可以省略的步驟。

詳細的過程不再贅述，在這裡隻進行簡要的說明。

已知主串的下标為 i i i, 子串的下标為 j j j， 總結下來是兩短句：“ i i i 不回溯， j j j 依 n e x t next next”。

i i i 不回溯：指的是在比對過程中，主串的比對下标永遠隻會增加或不變，不會再去比對之前主串的下标。

j j j 依 n e x t next next：指的是子串的下标比對規則是依照 n e x t next next 數組值。

那麼下面要詳細說明 n e x t next next 數組值是什麼。

n e x t next next 數組值推導

先給出數學式的定義：

n e x t [ j ] = { 0 , 當 j = 1時 M a x { k ∣ 1 < k < j ， 且 ′ p 1 . . . p k − 1 ′ = ′ p j − k + 1 . . . p j − 1 ′ } 當 此 集 合 不 空 時 1 ， 其他情況 next[j] = \begin{cases} 0, & \text{當 j = 1時} \\[2ex] Max\{ k | 1<k<j，且'p_1 ...p_{k-1}' ='p_{j-k+1}...p_{j-1}'\}& \text當此集合不空時\\[2ex] 1， & \text{其他情況} \end{cases} next[j]=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​0,Max{k∣1<k<j，且′p1​...pk−1′​=′pj−k+1​...pj−1′​}1，​當 j = 1時當此集合不空時其他情況​

e.g. T = “abcabx”

j 123456 模 式 串 T a b c a b x n e x t [ j ] 011123 \begin{array}{c|lcr} j & 123456 \\ \hline 模式串T & abcabx \\ next[j] & 011123 \end{array} j模式串Tnext[j]​123456abcabx011123​​

其中的一個子串"abcab", abcab，字首和字尾有兩個字元相等，則 n e x t [ 6 ] = 2 + 1 = 3 next[6] = 2 + 1 = 3 next[6]=2+1=3。

整個算法的時間複雜度時 O(n + m)，相較于樸素模式比對算法的 O((n - m + 1) * m)來說，較好一些（T的長度為m）。

KMP模式比對算法改進

一個例子：主串S = “aaaabcde”，子串T = “aaaaax”，其 next 數組值分别為 012345，在開始時，當 i = 5， j = 5時，我們發現"b" 與 "a"不想等，是以，j = next[5] = 4，此時 "b"與第四位置的"a"依然不等，j = next[4] = 3 … 這樣也會多出很多備援的步驟。是以，我們對求解next函數進行了改進。

在每次指派next的時候增加一個判斷，判斷 w h e t h e r   T [ i ] = = T [ j ] whether\ T[i] == T[j] whether T[i]==T[j]。

最後給出具體的python求解next數組的程式：

import numpy as np

def get_nextval(T):
    T = '#' + T
    i = 1
    j = 0
    nextval = np.zeros(len(T), dtype=int)
    
    while i < len(T)-1:
        if j == 0 or T[i] == T[j]:
            i = i + 1
            j = j + 1
            if T[i] != T[j]:
                nextval[i] = j
            else:
                nextval[i] = nextval[j]
        else: 
            j = nextval[j]
    nextval = np.delete(nextval,0)
    return nextval
           

− − − − − − − − − − − − − − − − ---------------- −−−−−−−−−−−−−−−−

該文章首發于 zyairelu.cn

歡迎來到我的網站進行評論及研讨

個人郵箱[email protected]

− − − − − − − − − − − − − − − − ---------------- −−−−−−−−−−−−−−−−