Python中BoyerMoore算法代码遇NameError：comparison未定义求助

首先，你遇到的两个核心问题是Python的变量作用域规则和函数返回值逻辑错误，咱们一步步拆解：

问题1：局部变量无法在函数外部访问 #

在Python中，函数内部定义的变量（比如comparison、match_table）属于局部变量，它们的作用域仅限于函数内部，函数执行结束后这些变量就会被销毁。所以你在__main__代码块里直接调用len(match_table)和print(comparison)会触发NameError——因为外部根本不知道这些变量的存在。

问题2：函数返回值逻辑错误 #

你的boyer_moore函数里写了两个return语句：

return match_table
return comparison

但函数执行到第一个return就会立刻终止，第二个return永远不会被执行，所以就算你能拿到返回值，也只能得到match_table，拿不到comparison的数值。

修复方案 #

我们可以让函数同时返回匹配结果列表和比较次数（Python支持返回多个值，本质是返回一个元组），然后在调用的时候接收这两个值。另外还要修正comparison的计数逻辑——你原来的代码只在完全匹配成功时加了1，实际每一次字符比较都应该计数，否则统计的比较次数是不准确的。

修改后的完整代码如下：

def make_bad_match_table(pattern):
    length = len(pattern)
    table = {}
    for i, c in enumerate(pattern):
        if i == length-1 and c not in table:
            table[c] = length
        else:
            table[c] = length - i - 1
    return table

def boyer_moore(pattern, text):
    comparison = 0
    match_table = []
    pattern_length = len(pattern)
    text_length = len(text)
    if pattern_length > text_length:
        return match_table, comparison
    table = make_bad_match_table(pattern)
    index = pattern_length - 1
    pattern_index = pattern_length - 1
    while index < text_length:
        comparison += 1  # 每一次字符比较都计数
        if pattern[pattern_index] == text[index]:
            if pattern_index == 0:
                match_table.append(index)
                pattern_index = pattern_length - 1
                index += (pattern_length * 2 - 1)
            else:
                pattern_index -= 1
                index -= 1
        else:
            index += table.get(text[index], pattern_length)
            pattern_index = pattern_length - 1
    # 同时返回匹配列表和比较次数
    return match_table, comparison

if __name__ == '__main__':
    with open("CNN.txt", "r") as file:  # 用with语句更安全，自动关闭文件
        target = file.read()
    pattern = "NASA"
    # 接收函数返回的两个值
    matches, compare_count = boyer_moore(pattern, target)
    print(f"Pattern '{pattern}' found at positions: {matches}")
    print(f"Total matches: {len(matches)}")
    print(f"Total comparisons: {compare_count}")

额外优化说明 #

1. 用with语句打开文件：这样不需要手动调用file.close()，文件会在代码块结束后自动关闭，避免资源泄漏。
2. 修正了comparison的计数逻辑：现在每一次字符对比都会增加计数，统计结果更准确。
3. 格式化输出：用f-string让打印的内容更易读。

内容的提问来源于stack exchange，提问作者madvic