News for hackers. Stuff that matters.
Re:New string search algorithm by zitterbewegung on Friday February 11, 2011 @07:22PM (#2208795)
This seems like a very practical website about the algorithm but where is the theory and proofs of the time complexity of the algorithm??
Re:New string search algorithm by dasht on Friday February 11, 2011 @09:16PM (#2209055)
I don't mean to be a turd but the proofs are kind of obvious on the face on this one. He's claiming expected linear time in the string being searched for "natural" texts and worst case O(MN). Proof of the worst case is pretty trivial by construction (of examples of that complexity) and contradiction (reaching the non-existence of worse cases). One can't be casual about proofs of course but: try thinking of an O(MN) example and then you can probably see from there why you can't do worse than that. Hint: if you can construct an example where you have to do the length M check for nearly every position in the length N haystack, aaaaaaaah... hmmmmm...., the rest should be clear.