> --somebody-- wrote:

>> initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.

> and you are basing this claim on…?

Think of it as an up-front cost that you expend before doing any actual work. So BM is slower in some cases, and faster in others. In most short cases the cost of setting up outweighs the advantages of the more complex algorithm and then you're better off to brute-force it.

The Moby-Dick example, however is not such a case.

Just like it takes longer to prepare an offset press to make a single copy of a page compared to just slapping it in to the photo-copier. But if you need a million copies, you can't beat (rotary) offset.

edit: I've re-constructed the original comment this replied to because I'm not happy about the recent trend in comment deletions (see below), that's the fourth time in a few days that I come across this. To the author of the parent of this comment (you know who you are), why did you delete your comment after receiving 3 serious replies?

Because he was probably downmodded (appropriately) for his comment, and considered it an embarrassment.

I'm not fond of such deletions, but I think it's good for people to be able to retract their statements when they realize they don't reflect well on themselves.

Perhaps a better solution would be to allow the original comment to be "retracted" such that the author information is removed but the comment remains, so people can still understand the thread of the conversation.

Retracting just the owner means you basically allow anonymous posting (except the mods still know who wrote it, and anyone who read it before the username got wiped). That opens up a whole new can of worms.

People can create an account with just a username and password; we're already effectively allowing anonymous posting.

Still, creating a throwaway account does present a certain barrier. In any case, this has been discussed to death previously.

The fact that computers use instructions in our universe?

Seriously, if you don't understand what he's basing his claim on, it's because you don't understand the Boyer-Moore algorithm. If you know how Boyer-Moore works, the reason is obvious. Instead of snarkily replying, why don't you take the same amount of time to read the wikipedia article on Boyer-Moore and see why brute force may be faster in some cases.

(Since you've already shown yourself to be lazy, however, I'll explain it: Boyer-Moore constructs two alphabet-sized integer arrays based on the "needle" you're looking for; if your haystack is smaller than twice your alphabet size, and it frequently is, then Boyer-Moore is practically guaranteed to take more time than brute force.)

Searching for "b" in "ab". Just two comparisons, compared to allocating, zeroing, and initializing a lookup table, and then doing a brute force search anyways. There's a fuzzy point where one becomes better than the other. Implementations written to be fast may brute-force length=1 strings, and implementations written for simplicity may not.