根据 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/