Hacker News new | past | comments | ask | show | jobs | submit login

There are literally hundreds of string search algorithms published now (including a large number of Boyer Moore variants).

There's a great resource called SMART for those interested in exploring this, with implementations of many of them and a simple benchmarking tool.

https://smart-tool.github.io/smart/

Although Boyer Moore is well known, there are generally faster algorithms available these days.

For short patterns, SHIFTOR will tend to be a lot faster than BM. Even the much simpler variant of BM, Horspool is usually faster than BM.

This highlights an interesting tension in search algorithm design. Often a simpler algorithm outperforms one with theoretically higher performance, but not always!




Fastest and best is the latest, EPSM. For all cases, given you are on x86_64 or aarch64 with sse4.2

The cited implementation has only minor problems, which I fixed in my fork.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: