后缀树模式匹配算法调试：find_occurrences函数输出异常

核心问题定位 #

你的find_occurrences函数之所以输出从0到最后匹配位置的所有索引，是因为在遍历后缀树时，错误地收集了模式匹配节点及其子树中所有后缀的起始索引，而没有筛选出仅对应模式完整出现的那些索引。

修复步骤 #

• 先确认模式完全匹配：遍历后缀树时，必须找到完全对应整个模式字符串的节点，只要中途某个字符不存在于当前节点的子节点中，直接返回空列表，避免后续错误收集。
• 精准收集有效索引：
  • 如果后缀树节点存储了后缀的结束位置end，可以通过公式start_idx = node.end - len(pattern)计算模式的起始索引（若文本索引从0开始）；
  • 如果节点直接存储后缀起始索引列表，要确保这些索引对应的后缀确实以目标模式开头——这一步需要在构建后缀树时就做好关联，只把符合条件的索引挂载到对应节点下。

修复后的代码示例 #

def find_occurrences(root, pattern, text_length):
    current_node = root
    # 先遍历树，确认模式完全匹配
    for char in pattern:
        if char not in current_node.children:
            return []
        current_node = current_node.children[char]
    
    occurrences = []
    # 遍历目标节点的所有叶子，收集有效起始索引
    def traverse_leaves(node):
        if node.is_leaf:
            # 计算模式起始位置：后缀结束位置 - 模式长度
            start_idx = node.end - len(pattern)
            occurrences.append(start_idx)
        else:
            for child in node.children.values():
                traverse_leaves(child)
    
    traverse_leaves(current_node)
    # 返回排序后的结果
    return sorted(occurrences)

关键注意事项 #

• 构建后缀树时，要保证每个节点关联的后缀索引，都是以该节点对应的字符串为前缀的后缀，避免无效索引混入；
• 绝对不要收集路径上所有节点的索引，只处理完全匹配模式的那个节点下的叶子索引。

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