3 ms·
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster! Anoth
by cperciva 16y ago
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
Another interesting bit of trivia: In the first chapter of my thesis I present a string matching algorithm with almost exactly the same asymptotic running time as BM -- but where BM performs exact matching using no precomputed index, my algorithm performs matching with mismatches using an index.
With an index, of course, exact matching is O(log N) time -- in a peculiar way, the "cost" of inexact matching is one index worth of efficiency.
[EDIT: On second thought, this last comment meaningful at all? I'm not sure, but it's almost 4AM so I'm not going to figure it out now.]
- jacquesm 16y agoIs your thesis online? I'd like to read that.
- cperciva 16y agoIs your thesis online? Yes, http://www.daemonology.net/papers/thesis.pdf http://www.daemonology.net/papers/thesis.pdf I'd like to read that. I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
- jacquesm 16y agoThank you! > I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious. And besides that is well over my head anyway, but I should be able to follow your main line of reasoning.
- auxbuss 16y agoI liked this: from your thesis: "If a mathematician is a machine for turning coffee into theorems, a computer scientist is a machine for converting caffeine into algorithms."
- kvs 16y agoColin, that is a well-written thesis I have read in a long time! Great work!