Python實現高效字符串查找功能

在實際的開發中，字符串查找功能是非常常見的需求。Python作為目前最流行的編程語言之一，也提供了非常豐富的字符串操作方法，其中包括高效的字符串查找功能。下面將從多個方面介紹Python如何實現高效的字符串查找。

一、基本字符串查找方法

在Python中最基礎的字符串查找方法就是利用字符串的find()方法。find()方法用於查找字符串中是否包含子字符串，如果包含則返回子字符串的起始位置，如果不包含則返回-1。

str = "hello world"
sub_str = "world"
result = str.find(sub_str)

if result != -1:
    print("子字符串起始位置為:", result)
else:
    print("在主字符串中找不到該子字符串")

通過這種方法可以完成基本的字符串查找功能，但對於大規模的字符串匹配操作來說，其效率較低。

二、KMP字符串查找算法

字符串的KMP算法是一種高效的字符串匹配算法。其核心思想是通過計算匹配子串的「部分匹配表」（partial match table）來實現查找，從而避免了重複匹配已經匹配的部分。下面是KMP字符串查找的Python實現。

def partial_match_table(sub_str):
    """計算子串的部分匹配表"""
    table = [-1] * len(sub_str)
    i, j = 0, -1

    while i < len(sub_str) - 1:
        if j == -1 or sub_str[i] == sub_str[j]:
            i += 1
            j += 1
            table[i] = j
        else:
            j = table[j]

    return table

def kmp_search(str, sub_str):
    """使用KMP算法查找子串在主串中的位置"""
    i, j = 0, 0
    table = partial_match_table(sub_str)

    while i < len(str) and j < len(sub_str):
        if j == -1 or str[i] == sub_str[j]:
            i += 1
            j += 1
        else:
            j = table[j]

    if j == len(sub_str):
        return i - j
    else:
        return -1

str = "hello world"
sub_str = "world"
result = kmp_search(str, sub_str)

if result != -1:
    print("子字符串起始位置為:", result)
else:
    print("在主字符串中找不到該子字符串")

可以看到，KMP算法相較於最基本的字符串查找方法，其效率有了大幅提升。相應的，計算「部分匹配表」所需的時間和空間複雜度也相對較高。

三、Boyer-Moore字符串查找算法

Boyer-Moore算法是另一種高效的字符串查找算法。其基本思想是從主串末尾開始匹配，如果匹配失敗，則根據預處理後的表格進行跳躍。由於是從末尾開始匹配，因此匹配失敗時跳躍的步數往往較多，從而避免了冗餘的匹配比較。

def boyer_moore_search(str, sub_str):
    """
    使用Boyer-Moore算法查找子串在主串中的位置
    """
    str_len = len(str)
    sub_str_len = len(sub_str)
    if sub_str_len == 0:
        return 0

    # 計算壞字符表格
    bad_char_table = {}
    for i in range(sub_str_len - 1):
        bad_char_table[sub_str[i]] = sub_str_len - i - 1

    # 計算好後綴表格
    suffix, prefix = suffix_prefix(sub_str)
    good_suffix_table = {}
    for i in range(sub_str_len):
        good_suffix_table[i] = sub_str_len - suffix[i]
    for i in range(sub_str_len - 1):
        j = suffix[i]
        if j != -1:
            k = sub_str_len - 1 - j
            if good_suffix_table[k] > i - j:
                good_suffix_table[k] = i - j

    # 開始匹配
    i = sub_str_len - 1
    while i = 0 and str[i] == sub_str[j]:
            i -= 1
            j -= 1
        if j == -1:
            return i + 1

        bad_char_step = bad_char_table.get(str[i], sub_str_len)
        good_suffix_step = good_suffix_table[sub_str_len - 1 - j]
        i += max(bad_char_step, good_suffix_step)

    return -1

def suffix_prefix(sub_str):
    """
    計算後綴表和前綴表
    """
    sub_str_len = len(sub_str)
    suffix = [-1] * sub_str_len
    prefix = [False] * sub_str_len
    for i in range(sub_str_len - 1):
        j = i
        k = 0
        while j >= 0 and sub_str[j] == sub_str[sub_str_len - 1 - k]:
            j -= 1
            k += 1
            suffix[k] = j + 1
        if j == -1:
            prefix[k] = True

    return suffix, prefix

str = "hello world"
sub_str = "world"
result = boyer_moore_search(str, sub_str)

if result != -1:
    print("子字符串起始位置為:", result)
else:
    print("在主字符串中找不到該子字符串")

使用Boyer-Moore算法可以極大地提高字符串查找的效率，同時其實現難度也較高。

四、總結

在Python中，實現高效的字符串查找可以使用多種算法，如基本的字符串查找方法、KMP算法和Boyer-Moore算法等。在實際的開發中，需要根據數據規模和性能要求選擇合適的算法來完成相應的字符串查找操作。