后缀树：在允许一定错误的情况下定位子串
根据维基百科关于后缀树的文章，后缀树可以用来找到一个字符串中的子字符串，前提是允许一定数量的错误。
如果我有一个字符串的后缀树，怎么才能找到这个字符串中所有给定子字符串的出现位置，并且每个位置最多允许一个错误呢？
（这里的“错误”指的是替换一个字符。）
1 个回答
4
这其实就是一种更复杂的图搜索方式（可以想象成在一个迷宫里找路，有些门坏了需要踢开，而你又想保护好自己的脚）。
具体的细节很大程度上取决于你所说的“错误”是什么意思。我理解“错误”是指替换一个字符，这种情况是最简单的。
在这个算法中，你会从树的根节点开始搜索，比较并推进你的模式，就像在找完全匹配一样。只不过如果遇到一个边上有个字符你无法继续，你就保存下算法的状态，以便后面使用（这个状态是指 [树的位置, 模式的位置]）。即使你可以跟随一个节点的某个链接，但不能跟随另一个链接，你也要继续跟随匹配的部分，并保存其他的状态。
接着，你回到之前保存的位置，模拟替换的过程，这意味着在树上向前移动一个位置（到所有不匹配的可能性）和在模式上向前移动一个位置。然后，继续正常搜索（因为你已经用掉了一个错误的机会，所以现在要找完全匹配）。
每当你到达模式的末尾，就报告成功匹配（也就是说，树中当前节点下面的所有叶子节点都是匹配的）。