[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>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?
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/