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算法相對於暴力算法而言，時間複雜度得到了極大的優化，可以更加高效地解決子字符串查找問題。