From: Daniel Fischer <[EMAIL PROTECTED]>
To: "Branimir Maksimovic" <[EMAIL PROTECTED]>
CC: Bulat Ziganshin <[EMAIL PROTECTED]>, 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/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
