在經典的模式匹配問題中，我們給出了長度為n的文本字符串T和長度為m的模式字符P，并希望明確是否P是T的一個字串。如果是，則希望找到P在T中開始位置的最低索引j，比如T[j:j+m]和P匹配，或者從T中找到所有的P的開始位置索引。

在本文中，我們介紹三種匹配算法，難度依次遞增。

1.暴力窮舉法

窮舉法是極其常用的一種算法，不止在匹配算法上，還在優化某些功能上也有涉及。

窮舉法即為列舉出所有的可能情況，并加以逐一判斷。

def find_brute(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)   # Get length of T and P's
    for i in range(n-m+1):  # Because it can't be P after T[n-m+1:]
        k = 0               # Record the index of P
        while k < m and T[i + k] == P[k]:   # The match was incomplete and successful
            k += 1
        if k == m:          # Match successful
            return i
    return -1

這是一個簡單的暴力枚舉的匹配算法，判斷P是否是T的一個子串，是則返回第一次出現的索引，否則返回-1，算法優化在不改變代碼結構的基礎上，就是這里扣一點，那里扣一點。例如range函數的范圍我們給出了n-m+1，因此對于P長度越大，則性能優化最大。

我們可以看到外層for循環至多執行了n-m+1次，內存while循環至多執行了m次，因此，該算法在最壞的情況下的運行時間是

測試一下：

T = "abcafgasdfwefacasdfe"
P = "asd"
print(find_brute(T, P))

運行結果：

2.Boyer-Moore算法

Boyer-Moore算法的主要思想是通過增加兩個可能省時的啟發式算法來提升窮舉法的運行時間：

1.鏡像啟發式（Looking-glass )：當測試P相對于T可能的位置時，可以從P的尾部開始比較，然后從后向前移動直到P的頭部。

2.字幕跳躍啟發式(-jump )：在測試P在T中可能的位置時，有著相應模式字符P[k]的文本字符T[i] = c的不匹配情況按如下方法處理：如果P中任何位置都不包含c，則將P完全移動到T[i]之后，(因為它不能匹配P中任何一個字符）；否則，直到P中出現字符c并與T[i]一致才移動P。

def find_boyer_moore(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)   # get length of T and P's
    if m == 0: return 0     # Return 0 if m's length is 0
    last = {}               # Create a dictionary for P
    for k in range(m):      # Add each character position of P to the dictionary
        last[P[k]] = k
        # align end of pattern at index m-1 of text
    i = m-1                 # This is a pointer to T
    k = m-1                 # This is a pointer to P
    while i < n:            # Use the while loop to iterate over T
        if T[i] == P[k]:    # If the match is successful and all matches
            if k == 0:
                return i

            else:           # If the match is successful but no all matches
                i -= 1      # Pointer forward
                k -= 1
        else:
            j = last.get(T[i], -1)
            # If the current character appears in the mode character,Return index ,else -1
            i += m - min(k, j+1)
            # Returns the starting pointer position by adding up the number of matched characters
            k = m-1
            # Restore k
    return -1

這段代碼的一個核心在于以下三條：

j = last.get(T[i], -1)
i += m - min(k, j+1)
k = m-1

通過字典last.get返回值判斷是否匹配成功過，如果字符在P中出現過，則返回索引（即還有多少個字符沒有匹配，然后通過m減去得到已經匹配的數量，在累加到i上，即可使i指針回到最初的位置，正常向后推進），否則返回-1，而在第二行中，使用了min函數判斷k和j+1的大小（如果沒有匹配到，則j+1得到0，m-0就會使指針i直接向后推進m個位置，極大程度上減少了運行速度。如果匹配成功過，則也可以通過min函數判斷k和j+1的大小使得m-min(k, j+1)能取得最大值）。
最后呢，將k還原為最開始的m-1.
如果使用傳統的查找表，在最壞的情況下BM算法的運行時間是o(nm)
測試一下

print(find_boyer_moore("abedef", "ede"))

運行結果：

3.Knuth-Morris-Pratt算法

KMP算法對于模式有一個確定的調整，如果發現一些匹配的字符但后來又發現不匹配，在模式下一次重新匹配時，我們忽略所有由成功的比較而獲得的信息。這樣避免了信息的浪費，并且它能達到的運行時間為

, 這是漸近最優運行時間。即在最壞的情況下，任何模式匹配算法將會對文本的所有字符和模式的所有字符檢查至少一次。KMP算法的主要思想是預先計算模式部分之間的自重疊，從而當不匹配發生在一個位置時，我們在繼續搜尋之前就能立刻知道移動模式的最大數目。

失敗函數

為了實現KMP算法，我們需要預先計算失敗函數

，該函數用于表示匹配失敗時P對應的位移。具體地，失敗函數f(k)定義為P的最長前綴的長度，它是P[1:K+1]的后綴（這里沒有包含P[0]，因為至少會移動一個單元）。如果在字符P[k+1]中找不到匹配，函數f(k)會告訴我們多少緊接著的字符可以用來重啟模式

def compute_kmp_fail(P):
    """Utility that computes and returns KMP 'fail' list."""
    m = len(P)
    fail = [0] * m          # by default. presume overlap of 0 everywhere
    j = 1
    k = 0

    while j < m:            # compute f(j) during this pass, if nonzero
        if P[j] == P[k]:    # k + 1 characters match thus fat
            fail[j] = k + 1
            j += 1
            k += 1
        elif k > 0:         # k follows a matching prefix
            k = fail[k-1]
        else:               # no match found starting at j
            j += 1
    return fail

這是一個失敗函數，通過雙指針來匹配最大的重復前綴，它將模式與KMP中的模式進行比較。每次有兩個匹配的字符，我們設置f(j0 = k + 1。因為在整個算法中已經有j > k，當使用它時，f(k - 1)總是被定義好的。

def find_kmp(T, P):
    """Return the lowest index of T at which substring P begins (or else -1)"""
    n, m = len(T), len(P)           # Get length of T and P's
    if m == 0: return 0             # Return 0 if P's length is 0
    fail = compute_kmp_fail(P)      # Call the compute_kmp_fail function to get the return list
    j = 0
    k = 0
    while j < n:
        if T[j] == P[k]:
            if k == m - 1:          # Complete match
                return j - m + 1    # Return the index of the first matched character
            j += 1                  # Match successful but no all, pointer forward
            k += 1
        elif k > 0:                 # Match failure but succeeded
            k = fail[k - 1]         # Prefix rebound
        else:
            j += 1
    return -1

這是一個KMP算法的實現，其中 k = fail[k-1]實現了不完全匹配時觸發的前綴回跳，以此來減少匹配次數，實現算法優化。不太理解的可以打個斷點觀察一下k的變化。

測試一下：

print(find_kmp("ababababef", "ababef"))

運行結果：