[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>From: "Branimir Maksimovic" <bmaxa at hotmail.com>
>To: daniel.is.fischer at web.de
>CC: Haskell-Cafe at haskell.org
>Subject: Re: [Haskell-cafe] Substring replacements
>Date: Thu, 15 Dec 2005 00:55:02 +0000
>
>
>
>
>>From: Daniel Fischer <daniel.is.fischer at web.de>
>>To: "Branimir Maksimovic" <bmaxa at hotmail.com>
>>CC: Haskell-Cafe at haskell.org
>>Subject: Re: [Haskell-cafe] Substring replacements
>>Date: Wed, 14 Dec 2005 20:40:06 +0100
>>
>>Hi Bane,
>>
>>nice algorithm. Since comparing chars _is_ cheap, it is to be expected 
>>that
>>all the hash-rotating is far more costly for short search patterns. The
>>longer the pattern, the better this gets, I think -- though nowhere near 
>>KMP
>>(or would it?).
>
>Yes,KMP is superior in single pattern search. We didn't tried Boyer-Moore
>algorithm yet, though. But I think it would be
>difficult to implement it in Haskell efficiently as it searches backwards
>and jumps around, and we want memory savings.
>Though, I even didn't tried yet, but it is certainly very interesting.
>

Forget what I've said.
Boyer-Moore *can* be implemented efficiently, it is similar to KMP it goes
forward, but when it finds last character in pattern, than starts to search 
backwards.
This can be implemented easilly as Haskell lists naturaly reverse order
when putting from one list to other.
Heh, never say never :)
As I see from documents Boyer-Moore has best performance on average
and should be better than KMP.

Greetings,Bane.

_________________________________________________________________
FREE pop-up blocking with the new MSN Toolbar - get it now! 
http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/