Have you ever used KMP or BM algorithms?

Question

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.

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

Answer 1

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.

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 beat the brute force method.

There is always a trade off 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.