字符串匹配算法：KMP算法、Boyer-Moore算法与Rabin-Karp算法

字符串匹配是在文本中查找特定子串的过程。有许多不同的字符串匹配算法，其中最著名的三种是Knuth-Morris-Pratt（KMP）算法、Boyer-Moore算法和Rabin-Karp算法。这些算法在处理大型文本或模式串时，提供了比暴力匹配更好的性能。

1. KMP算法
   KMP算法是一种高效的字符串匹配算法，由Donald Knuth、Vaughan Pratt和James H. Morris三人共同提出。KMP算法的核心思想是利用已经匹配失败的信息，避免不必要的字符比较。算法通过一个称为“部分匹配表”或“失败函数”的数据结构来记录已经匹配过的字符。当模式串中的某个字符与目标字符串不匹配时，部分匹配表可以帮助算法跳过某些不必要的字符比较。

下面是一个使用Python实现的KMP算法示例：

def kmp_search(target, pattern):
    prefix_table = generate_prefix_table(pattern)
    i = 0  # index for target string
    j = 0  # index for pattern string
    while i < len(target):
        if pattern[j] == target[i]:
            i += 1
            j += 1
        if j == len(pattern):
            return i - j  # found the pattern, return the start index
        elif i < len(target) and pattern[j] != target[i]:
            if j != 0:
                j = prefix_table[j - 1]
            else:
                i += 1
    return -1  # pattern not found in the target string
def generate_prefix_table(pattern):
    prefix_table = [-1] * len(pattern)
    j = -1  # index for prefix table
    for i in range(1, len(pattern)):
        while j > -1 and pattern[j] != pattern[i]:
            j = prefix_table[j]
        if pattern[j] == pattern[i]:
            j += 1
        prefix_table[i] = j
    return prefix_table

1. Boyer-Moore算法
   Boyer-Moore算法是另一种高效的字符串匹配算法，由R. A. Boyer和S. M. Moore于1977年提出。该算法通过构建坏字符规则和好后缀规则来优化匹配过程。坏字符规则允许算法在遇到不匹配的字符时跳过尽可能多的字符，而好后缀规则则允许算法在遇到部分匹配的子串时跳过尽可能多的字符。Boyer-Moore算法的平均时间复杂度为O(n/m)，其中n是目标字符串的长度，m是模式串的长度。

下面是一个使用Python实现的Boyer-Moore算法示例：

```python
def boyer_moore_search(target, pattern):
bad_char_table = build_bad_char_table(pattern)
good_suffix_table = build_good_suffix_table(pattern)
i = 0 # index for target string
j = len(pattern) - 1 # index for pattern string (start from the end)
while i <= len(target) - 1:
if pattern[j] == target[i]:
i += 1
j -= 1
if j == -1:
return i # found the pattern, return the start index
bad_char = bad_char_table.get(target[i], -1) # get bad character index in pattern string, if not found, return -1
if bad_char != -1 and bad_char < j: # if the bad character index is less than current index j, update j to the last index of bad character’s last occurrence in pattern string (or the last index of last suffix in good suffix table if it’s a good suffix)
j = max(bad_char, good_suffix_table.get(j + 1, -1))
else: # if the bad character index is not less than current index j, just do the normal comparison (without updating j)
if target[i] == pattern[j]: # if the current character is