boyer-moore算法的python代码

以下是 Boyer-Moore 算法的 Python 代码实现：

def bad_character_table(pattern):
    # 构建坏字符哈希表
    table = {}
    for i in range(len(pattern)):
        table[pattern[i]] = i
    return table

def good_suffix_table(pattern):
    # 构建好后缀哈希表
    table = [-1] * len(pattern)
    for i in range(len(pattern)):
        j = i - 1
        while j >= 0 and pattern[j:j+len(pattern)-i] == pattern[i:]:
            j -= 1
        table[len(pattern)-i-1] = j+1
    return table

def boyer_moore(text, pattern):
    m, n = len(pattern), len(text)
    if m > n:
        return -1
    bad_char_table = bad_character_table(pattern)
    good_suffix_table = good_suffix_table(pattern)
    i = 0
    while i <= n-m:
        j = m-1
        while j >= 0 and pattern[j] == text[i+j]:
            j -= 1
        if j == -1:
            return i
        bad_char_index = bad_char_table.get(text[i+j], -1)
        i += max(j - bad_char_index, good_suffix_table[m-j-1])
    return -1

其中，`bad_character_table` 函数用于构建坏字符哈希表，`good_suffix_table` 函数用于构建好后缀哈希表，`boyer_moore` 函数用于实现 Boyer-Moore 算法的主体部分。在 `boyer_moore` 函数中，首先判断模式串长度是否大于文本串长度，若是则返回 -1。接着，分别构建坏字符哈希表和好后缀哈希表，并将游标 i 指向文本串的起始位置。在循环中，游标 j 从模式串结尾处向前匹配，若匹配成功则 j 减一，否则通过坏字符哈希表和好后缀哈希表计算出新的游标 i，并将游标 j 重置为模式串结尾。最终，若未能匹配则返回 -1。