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

Question

根据维基百科关于后缀树的文章，如果允许一定数量的错误，后缀树可用于定位字符串的子字符串。

给定字符串的后缀树，我怎样才能找到它的给定子字符串的所有实例，而每个实例最多允许一个错误？

（“错误”是指替换一个字符。）

Answer 1

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

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

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

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

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