Python實現高效字元串匹配

在Python中，字元串匹配是一項廣泛使用的任務。然而，由於字元串匹配的複雜性，它往往是計算資源密集型的任務。在本文中，我們將介紹幾種高效的方法，能夠幫助加速Python的字元串匹配任務。

一、樸素演算法

在我們介紹更高效的字元串匹配演算法之前，首先讓我們來看看樸素演算法。該演算法非常簡單，它只是通過迭代暴力檢查一個文本串中的每個可能匹配的位置，以查找模式串的出現。

def naive_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    for i in range(text_len - pattern_len + 1):
        j = 0
        while j < pattern_len and text[i+j] == pattern[j]:
            j += 1
        if j == pattern_len:
            return i
    return -1

以上代碼中的naive_search函數實現了樸素演算法。該演算法通過兩個嵌套的循環來遍歷文本串和模式串，最壞的情況下時間複雜度為O(n*m)，其中n和m分別為文本串和模式串的長度。

二、KMP演算法

KMP演算法是一種高效的字元串匹配演算法。它的核心思想是利用模式串中已經匹配的信息，儘可能地減少文本串的比較次數。在KMP演算法中，我們需要首先計算一個模式串的前綴函數。前綴函數的定義如下：

對於模式串P的長度為n的前綴子串，定義其前綴函數π[i]的值為P的前i個字元組成的字元串的最長相等真前綴和真後綴的長度。 即π[i] = max{k: 1 ≤ k < i, P[0:k] = P[i-k:i]}

def kmp_prefix(pattern):
    pattern_len = len(pattern)
    pi = [0] * pattern_len
    k = 0
    for q in range(1, pattern_len):
        while k > 0 and pattern[k] != pattern[q]:
            k = pi[k - 1]
        if pattern[k] == pattern[q]:
            k += 1
        pi[q] = k
    return pi

def kmp_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    pi = kmp_prefix(pattern)
    q = 0
    for i in range(text_len):
        while q > 0 and pattern[q] != text[i]:
            q = pi[q - 1]
        if pattern[q] == text[i]:
            q += 1
        if q == pattern_len:
            return i - pattern_len + 1
    return -1

以上代碼中的kmp_prefix函數返回模式串的前綴函數，kmp_search函數實現了KMP演算法，通過利用前綴函數匹配過程中的信息，它的時間複雜度為O(n+m)。

三、Boyer-Moore演算法

Boyer-Moore演算法是一種採取多種啟發式策略的高效字元串匹配演算法。它的思路是儘可能地跳過文本串中完全不可能匹配的部分，從而減少匹配所需的比較次數。該演算法主要運用了以下兩個啟發式策略：

• 壞字元啟發：當發現不匹配時，移動模式串儘可能地靠右，從而儘可能地跳過不可能匹配的字元。
• 好後綴啟發：當發現不匹配時，移動模式串使得匹配的部分對齊好後綴，從而儘可能地利用已經匹配的信息。

def bad_char_shift(pattern):
    shift = [None] * 256
    pattern_len = len(pattern)
    for i in range(pattern_len):
        shift[ord(pattern[i])] = i
    return shift
    
def bm_suffixes(pattern):
    pattern_len = len(pattern)
    suff = [0] * pattern_len
    j = pattern_len - 1
    i = 0
    while j >= 0:
        if pattern[j] == pattern[i]:
            suff[j] = i + 1
            j -= 1
            i += 1
        else:
            i = 0
            j -= 1
    return suff

def bm_preprocess(pattern):
    shift = bad_char_shift(pattern)
    suff = bm_suffixes(pattern)
    return shift, suff
    
def bm_search(text, pattern):
    text_len = len(text)
    pattern_len = len(pattern)
    if pattern_len == 0:
        return 0
    shift, suff = bm_preprocess(pattern)
    i = 0
    while i = 0 and pattern[j] == text[i+j]:
            j -= 1
        if j < 0:
            return i
        else:
            char_shift = j - shift[ord(text[i+j])] if shift[ord(text[i+j])] is not None else j + 1
            suff_shift = suff[j]
            i += max(char_shift, suff_shift)
    return -1

以上代碼中的bm_preprocess函數進行了Boyer-Moore演算法的預處理，bm_search函數實現了Boyer-Moore演算法。該演算法可以在最壞情況下實現O(n*m)時間複雜度，但在實際應用中通常運行速度要優於其他演算法。