字符串匹配算法的扩展：从单模式匹配到多模式匹配

# 1. 字符串匹配算法基础**

字符串匹配算法是计算机科学中的一类重要算法，用于在给定文本中查找特定模式。字符串匹配算法在许多应用中都有广泛的应用，例如文本搜索、网络入侵检测和生物信息学。

字符串匹配算法的基本原理是将模式与文本进行比较，并确定模式在文本中出现的位置。字符串匹配算法的效率至关重要，因为它们经常用于处理大量数据。

字符串匹配算法有多种类型，每种算法都有其独特的优势和劣势。最常见的字符串匹配算法包括朴素字符串匹配算法、KMP算法和BM算法。这些算法将在下一章中详细讨论。

# 2. 单模式匹配算法

### 2.1 朴素字符串匹配算法

朴素字符串匹配算法是最简单的一种字符串匹配算法，其基本思想是逐个字符比较模式串和目标串，当发现不匹配时，将模式串右移一位，继续比较。算法的具体步骤如下：

def naive_string_matching(text, pattern):
    """
    朴素字符串匹配算法

    参数：
        text: 目标字符串
        pattern: 模式字符串

    返回：
        模式串在目标串中首次出现的位置，如果没有找到则返回 -1
    """
    n = len(text)
    m = len(pattern)

    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i

    return -1

**逻辑分析：**

* `n` 和 `m` 分别表示目标串和模式串的长度。
* 外层循环遍历目标串中所有可能的匹配位置，从索引 `i` 开始。
* 内层循环比较目标串从索引 `i` 开始的 `m` 个字符和模式串。
* 如果比较结果相等，则返回 `i`，表示模式串在目标串中首次出现的位置。
* 如果外层循环遍历完所有位置都没有找到匹配，则返回 `-1`。

### 2.2 KMP算法

KMP算法（Knuth-Morris-Pratt算法）是一种改进的字符串匹配算法，它使用一个称为失败函数的预处理表来优化比较过程。失败函数存储了模式串中每个字符匹配失败后，模式串应该右移的距离。

def kmp_string_matching(text, pattern):
    """
    KMP字符串匹配算法

    参数：
        text: 目标字符串
        pattern: 模式字符串

    返回：
        模式串在目标串中首次出现的位置，如果没有找到则返回 -1
    """
    n = len(text)
    m = len(pattern)
    failure_function = build_failure_function(pattern)

    i = j = 0

    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            return i - j

        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = failure_function[j - 1]
            else:
                i += 1

    return -1

def build_failure_function(pattern):
    """
    构建失败函数

    参数：
        pattern: 模式字符串

    返回：
        失败函数表
    """
    m = len(pattern)
    failure_function = [0] * m

    i = 1
    j = 0

    while i < m:
        if pattern[i] == pattern[j]:
            failure_function[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = failure_function[j - 1]
        else:
            failure_function[i] = 0
            i += 1

    return failure_function

**逻辑分析：**

* `n` 和 `m` 分别表示目标串和模式串的长度。
* `failure_function` 是一个长度为 `m` 的列表，存储了模式串中每个字符匹配失败后应该右移的距离。
* 外层循环遍历目标串。
* 内层循环比较目标串和模式串的字符。
* 如果比较结果相等，则更新 `i` 和 `j`。
* 如果模式串匹配失败，则根据失败函数更新 `j`。
* 如果模式串匹配成功，则返回模式串在目标串中首次出现的位置。

### 2.3 BM算法

BM算法（Boyer-Moore算法）是一种高效的字符串匹配算法，它使用一种称为坏字符规则和好后缀规则的启发式方法来优化比较过程。

def bm_string_matching(text, pattern):
    """
    BM字符串匹配算法

    参数：
        text: 目标字符串
        pattern: 模式字符串

    返回：
        模式串在目标串中首次出现的位置，如果没有找到则返回 -1
    """
    n = len(text)
    m = len(pattern)
    bad_character_table = build_bad_character_table(pattern)
    good_suffix_table = build_good_suffix_table(pattern)

    i = m - 1

    while i < n:
        j = m - 1

        while j >= 0 and pattern[j] == text[i]:
            j -= 1
            i -= 1

        if j == -1:
            return i + 1

        else:
            shift = max(bad_character_table[text[i]], good_suffix_table[j])
            i += shift

    return -1

def build_bad_character_table(pattern):
    """
    构建坏字符表

    参数：
        pattern: 模式字符串

    返回：
        坏字符表
    """
    bad_character_table = {}

    for i in range(256):
        bad_character_table[i] = m

    for i in range(m - 1):
        bad_character_table[ord(pattern[i])