[Haskell-cafe] Substring replacements

Branimir Maksimovic 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 

Greetings, Bane.

Express yourself instantly with MSN Messenger! Download today it's FREE! 

More information about the Haskell-Cafe mailing list