algorithm - 使用 bitap 算法寻找模糊匹配

Question

最近，我已经查看了 bitap 算法的几种实现，但它们所做的都是找到模糊匹配的起点。我需要的是找到一个匹配。有一个例子：

假设我们有以下文本：abcdefg

和一个模式：bzde

并且我们希望在文本中找到所有出现的模式，最多有 1 个错误（考虑编辑距离）。

所以我需要算法返回：bcde。

有没有简单（或不简单=））的方法来做到这一点？关于这个算法的原始文章没有回答这个问题。

谢谢您的帮助。

Answer 1

作为一个简单的开始，您可以使用一系列正则表达式来处理它，在每个表达式中，您将 1 个字符替换为.通配符。使用构造将这些表达式组合成一个( | )以创建一个大的正则表达式。

另一种方法是扫描字符串，保持错误计数并在遇到太多错误时增加匹配的偏移量。