串的模式匹配bf算法代码

在计算机科学中，BF（Boyer-Moore）算法是一种著名的字符串搜索算法，用于高效地查找一个文本串是否包含另一个固定模式串。该算法的基本思想是在搜索过程中跳过不必要的字符比较，减少了不必要的比较次数。

以下是基本的BF算法的Python代码示例：

def bad_char_search(pattern, text):
    m = len(pattern)
    n = len(text)

    # 计算坏字符表，存储每个字符相对于模式的位置偏移
    bad_chars = {char: -1 for char in pattern}

    i = m - 1
    while i < n:
        j = m - 1
        while j >= 0 and text[i] == pattern[j]:
            j -= 1
        if j == -1:
            return i
        else:
            # 如果当前字符与模式不符，向右移动并更新bad_chars
            skip_distance = max(1, abs(bad_chars[text[i]] or m))
            i += skip_distance

    return -1  # 没有找到匹配

# 使用例子
pattern = "abc"
text = "abcdefgabc"
match_index = bad_char_search(pattern, text)
if match_index != -1:
    print(f"Pattern found at index {match_index}")
else:
    print("Pattern not found")

在这个代码中，`bad_char_search`函数首先创建了一个bad_chars字典，然后从文本的末尾开始遍历，利用bad_chars表中的信息快速跳过不匹配的字符。当找到一个匹配时，返回其位置；如果没有找到，则返回-1表示未找到。