Re: [Haskell-cafe] Substring replacements

From: Daniel Fischer To: "Branimir Maksimovic" CC: Bulat Ziganshin , Haskell-Cafe@haskell.org

...

KMP is O(m) while straightforward is O(m*n).

Where m is the length of the input and n is the length of the searched-for pattern, I think? Yes. But these are worst-case complexities, I believe, ordinarily, straightforward will be O(m), too.

Yes, those are worst cases for both algorithms. O(m) for KMP, O(m*n) for straightforward.

...

My test favors straightforward, in any other case KMP wins by order of magnitude. Can you give example tests?

Any example that has long search pattern say (many a's followed by b ) and searched string has many partial matches (many a's). Particularly, any example which exhibits O(m*n) or close to, case for straightforward search. Greetings, Bane. _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/