[Haskell-cafe] Substring replacements
bmaxa at hotmail.com
Wed Dec 21 12:05:05 EST 2005
>From: Daniel Fischer <daniel.is.fischer at web.de>
>To: "Branimir Maksimovic" <bmaxa at hotmail.com>
>CC: Bulat Ziganshin <bulatz at HotPOP.com>, Haskell-Cafe at 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?
>But these are worst-case complexities, I believe, ordinarily,
>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
Express yourself instantly with MSN Messenger! Download today it's FREE!
More information about the Haskell-Cafe