Python實現高效的子字元串查找演算法

一、子字元串查找演算法介紹

子字元串查找問題指的是在一個較長的字元串中查找特定的子字元串。在實際應用中，子字元串查找問題很常見，包括文本的搜索、語音識別、數據壓縮等等。因此，如何高效地解決子字元串查找問題成為一個十分重要的問題。

常見的子字元串查找演算法有暴力演算法、KMP演算法、Boyer-Moore演算法等。暴力演算法的時間複雜度是O(nm)，其中n是文本串的長度，m是模式串的長度，因此在大規模數據中效率比較低。KMP演算法和Boyer-Moore演算法則能夠更高效地解決子字元串查找問題。

二、KMP演算法介紹

KMP演算法（Knuth-Morris-Pratt演算法）是一種匹配字元串的演算法。該演算法是由Donald Knuth、Vaughan Pratt和James H. Morris於1977年聯合發表的。KMP演算法通過利用之前已經部分匹配這個有效信息，儘可能減少模式串與文本串的匹配次數以達到快速匹配的目的。KMP演算法的時間複雜度是O(n+m)，其中n是文本串的長度，m是模式串的長度。

KMP演算法的核心思想是利用已有的部分匹配信息，找到在模式串失配後應該跳到哪個位置繼續匹配。當模式串與文本串中的某個字元不匹配時，我們需要「回退」模式串中的指針，讓模式串移動到合適的位置，再繼續匹配。

三、KMP演算法的Python實現

接下來，我們將通過代碼示例來展示KMP演算法的Python實現。

def kmp_search(text, pattern):
    """
    KMP演算法，查找pattern在text中的位置
    :param text: 文本串
    :param pattern: 模式串
    :return: 若存在返回第一個下標，否則返回-1
    """
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    # 構建next數組
    next = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[j] != pattern[i]:
            j = next[j-1]
        if pattern[j] == pattern[i]:
            j += 1
        next[i] = j

    # 在text中查找pattern
    j = 0
    for i in range(n):
        while j > 0 and pattern[j] != text[i]:
            j = next[j-1]
        if pattern[j] == text[i]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

text = "ABABABBBABAABABA"
pattern = "ABA"
print(kmp_search(text, pattern))  # 0

text = "hello, world"
pattern = "world"
print(kmp_search(text, pattern))  # 7

text = "hello, world"
pattern = "abc"
print(kmp_search(text, pattern))  # -1

以上是KMP演算法的Python實現示例。我們可以看到KMP演算法相對於暴力演算法而言，時間複雜度得到了極大的優化，可以更加高效地解決子字元串查找問題。