News for hackers. Stuff that matters.

A comment on The Boyer-Moore Fast String Searching Algorithm. Parent comment

Re:The Boyer-Moore Fast String Searching Algorithm by lofi_lory on Friday April 23, 2021 @09:59AM (#26914846)
Yes, I am not contesting or anything, but my example shows how the original BC and GS rules don't protect you from quadratic worst case complexity either. That's my point, it's not easy to do sub-quadratic worst case search.

I haven't recently looked into the sub-quadratic worst case improved version of BM, but IIRC it's far from trivial and not what most people think of for this algorithm. I assume it's also slower IRL, for cache misses, or for expensive operations like modulo in the main loop, and prolly has a space penalty.

BM just has a better average case than naive string search.

[ Parent | on HN ]
Re:The Boyer-Moore Fast String Searching Algorithm by taeric on Friday April 23, 2021 @10:09AM (#26914934)
Burntsushi has plenty of data showing it isn't the best nowadays. Pretty sure any version that goes quadratic is bite BM, though. Not that you are wrong, but just highlighting that most folks don't think of BM when they think they are, though.
[ Parent | on HN ]