4 ms·

Boyer-Moore string searching is a good example of a simple but non-obvious "idea" (search backwards; it's much faster). http://www.cs.utexas.edu/users/moore/be

• barrkel 18y ago
  Boyer-Moore is far from non-obvious. I remember having the same basic idea when I was a kid, when I was programming on the C64 and before I had access to the internet or decent programming books. The details - e.g. jump distances based on whether and where the characters occur in the search string etc. - come up in trying to create a working implementation.
  • 11ren 18y ago
    I tend to think that ideas are a dime a dozen, and actually doing it is what makes the difference - Boyer-Moore is one of the few counter-examples. But if you also had the idea... could it be that you're unusually smart? The details of Boyer-Moore seem obvious to me, in that you bump into them in trying to get it working, even if you don't foresee them. They are like workshop improvements. Did you manage to implement a version of it, as a kid? Or is this another instance of showing that actually doing it is what counts?
    • jhancock 18y ago
      Our "idea" legal structure (patents, copyrights, etc) is not about ideas at all. Its about commerce. All that matters is implementation in a manner that increases money exchange. Everything is optimized around that, or is supposed to be. An idea itself is of little value. If it were, the really hard stuff, like math itself, would be patentable.
• kragen 18y ago
  If you had implemented a simple string search, and then someone told you that it was usually possible to do a string search without examining all the characters of the string, you'd probably come up with some Boyer-Moore variant. Nevertheless it took decades for people to come up with it. It's one of those cases where the basic idea is the really hard part. Binary search, among the very basic algorithms, is toward the other extreme. An incorrect version of the algorithm was published something like 20 years before a bug-free version was published.