根据Wikipedia article on suffix trees ，如果允许一定数量的错误，后缀树可用于定位字符串的子串。
给定一个字符串的后缀树，我如何找到它的给定子串的所有实例，允许每个实例最多有一个错误？
(“错误”是指替换了一个字符。)
最佳答案
那将只是一个更复杂的图形搜索(也就是找到穿过地牢的路径，其中一些门坏了，需要踢开，你想腾出脚)。
细节在很大程度上取决于您所说的“错误”是什么意思。所以我认为“错误”是一个字符的替换，这是最简单的情况。
在该算法中，您将从根开始搜索树，比较并推进您的模式，就好像您搜索完全匹配一样。就在边缘上有一个您无法跟随的字符时，您可以保存算法的状态以备后用(状态为 [tree position, pattern position])。即使您可以为一个节点跟踪一个链接，但不能为另一个节点跟踪，这也应该适用 - 您跟踪匹配并保存其他节点。
然后，您返回到保存的位置并模拟替换，这意味着在树中前进一个位置(对于所有不匹配的可能性)和模式中的一个位置。然后，继续正常搜索(您已经排除了出现一个错误的可能性，因此您现在正在搜索完全匹配项)。
每当您到达模式的末尾时，报告匹配成功(即树中当前节点下方的所有叶子)。
关于python - 后缀树 : locating a substring if a certain number of mistakes are allowed，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9310923/