你曾经使用KMP或BM算法？ [英] Have you ever used KMP or BM algorithms?

问题描述

我知道KMP（克努特 - 莫里斯 - 普拉特）和BM（Boyers - 穆尔）算法等都是不错的字符串搜索操作的算法。 我也知道，BM比KMP快3-5倍。

I know KMP (Knuth–Morris–Pratt) and BM (Boyers-Moore) algorithms are all good string search operation algorithms. I also know that BM is 3-5 times quicker than KMP.

在你的编程软件行业的经验，你有没有使用BM或KMP算法？ 是否真的算法的事吗？

In your experience of programming for industry software, have you ever used BM or KMP algorithms? Does the algorithm really matter here?

推荐答案

如果你看一下，例如Java的String.indexOf功能，似乎他们使用蛮力方法字符串匹配。 你可能想知道这是为什么。

If you have a look at for example Java's String.indexOf function it seems that they use the brute force method for string matching. You may wonder why that is.

的原因是，在这些算法执行的一些查询$​​ P $ pprocessing和（如果使用两个阵列尤其对于BM），其可能是昂贵的。因此，您在搜索字符串必须是大尺寸的KMP和BM之前，甜菜强力法。

The reason is that some query preprocessing is performed in these algorithms and that may be costly (especially for BM if you use both arrays). Therefore the strings you search in must be of a large size before KMP and BM can beet the brute force method.

总是有使用不同算法时，当与大型字符串处理，你可以考虑的文本而不是查询索引以及（如后缀树）的交易。这时候，你每次都处理新的文本，甚至可能是有益的。

There is always a trade of when using different algorithms and when dealing with large strings you may consider indexing of the text instead of the query as well (e.g. suffix trees). This may even be useful when you deal with new texts each time.

在我看来，这些算法，而大专院校，只有在特殊情况下非常有用。

In my opinion these algorithms are rather academical and only useful under special circumstances.

这篇关于你曾经使用KMP或BM算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！