algorithm - 你用过 KMP 或 BM 算法吗？

Question

我知道 KMP (Knuth–Morris–Pratt) 和 BM (Boyers-Moore) 算法都是很好的字符串搜索运算算法。我也知道 BM 比 KMP 快 3-5 倍。

在您的行业软件编程经验中，您使用过 BM 或 KMP 算法吗？算法在这里真的很重要吗？

Answer 1

如果您看一下 Java 的 String.indexOf 函数，您会发现它们似乎使用强力方法进行字符串匹配。您可能想知道为什么会这样。

原因是在这些算法中执行了一些查询预处理，这可能代价高昂(尤其是对于 BM，如果您同时使用两个数组)。因此，在 KMP 和 BM 可以击败蛮力方法之前，您搜索的字符串必须很大。

在使用不同的算法时总是需要权衡取舍，并且在处理大字符串时，您可能会考虑对文本而不是查询进行索引(例如后缀树)。当您每次处理新文本时，这甚至可能很有用。

在我看来，这些算法相当学术化，只有在特殊情况下才有用。