后缀树：如果允许一定数量的错误，则定位子字符串

Question

根据Wikipedia article on suffix trees，如果允许一定数量的错误，后缀树可以用来定位字符串的子字符串。在

给定一个字符串的后缀树，如何找到它的给定子字符串的所有实例，允许每个实例最多有一个错误？在

（我所说的“错误”是指替换一个字符。）

Answer 1

这将是一个更复杂的图形搜索（也可以找到穿过地牢的路径，在那里有些门被打破，需要被踢开，你想省省你的脚）。在

细节在很大程度上取决于你所说的“错误”是什么意思。所以我认为“错误”是一个字符的替换，这是最简单的情况。在

在算法中，您将从根目录搜索树，比较并推进您的模式，就像您搜索了完全匹配一样。如果边缘上有一个您无法跟踪的字符，您可以保存算法的状态以备以后使用（状态为[tree position, pattern position]）。即使你可以跟踪一个节点的一个链接，而不是另一个链接，这一点也应该适用——你遵循匹配并保存其他链接。在

然后，返回到保存的位置并模拟替换，这意味着在树中前进一个位置（所有不匹配的可能性）和模式中的一个位置。然后，继续正常搜索（您已经消耗了一个错误的可能性，所以您现在正在搜索完全匹配的内容）。在

每当到达模式的末尾时，报告匹配成功（即树中当前节点下的所有叶子）。在