Boyer-Moore算法用python实现

好的，以下是Boyer-Moore算法的Python实现：

def boyer_moore(text, pattern):
    # 计算字符集大小
    alphabet = set(text)
    # 初始化坏字符表
    bad_char = {c: pattern.rfind(c) for c in alphabet}
    # 初始化好后缀表
    m = len(pattern)
    suffix, prefix = [0] * m, [-1] * m
    for i in range(m - 1):
        j = i
        while j >= 0 and pattern[j] == pattern[m - 1 - i + j]:
            j -= 1
            suffix[i] = i - j
        if j == -1:
            prefix[i] = True
    j = 0
    while j <= len(text) - m:
        i = m - 1
        while i >= 0 and pattern[i] == text[i + j]:
            i -= 1
        if i < 0:
            return j
        # 坏字符规则
        if text[i + j] in bad_char:
            j += max(1, i - bad_char[text[i + j]])
        else:
            j += i + 1
        # 好后缀规则
        if i == m - 1:
            k = 0
        else:
            k = suffix[i + 1]
        j += max(k, prefix[m - 1 - i])
    return -1

其中，`text`参数表示文本串，`pattern`参数表示模式串，返回值是模式串在文本串中的起始位置。这个实现中使用了坏字符规则和好后缀规则，在匹配过程中先匹配坏字符，然后匹配好后缀，以尽可能地减少比较次数。