Branimir Maksimovic bmaxa at hotmail.com
Thu Dec 15 13:21:48 EST 2005

```This is what I got for BM. Performance dissapoints as BM is really
suited for indexed strings like arrays.It mainly operates on indexes.
This is simple BM, as I didn't want to go
for more complex variant,becauses takes and drops and recalculation of next
position
is too pricey for non indexed structure. So, clear winner is KMP for
non indexed strings. There is also finite automaton algorithm
but this works well if search strings are precompiled, so I'll
implement it only for education purposes. I hope my Haskell improves
as I've learned how to reduce number of paramaters.

searchReplaceBM :: String -> String -> String -> String
searchReplaceBM "" _ str = str
searchReplaceBM sr rp str = searchReplace str
where
table :: UArray Int Int
table  = array (0,255) ([(i,0) | i <- [0..255]] ++ proc sr 1)
proc [] _ = []
proc (s:st) i = (ord s,i):proc  st (i+1)
len = length sr
rsrch = reverse sr
searchReplace str
| null remaining = if found then rp
else passed
|found = rp ++ searchReplace remaining
| otherwise = passed ++ searchReplace remaining
where
(passed,remaining,found) = searchReplace' str
searchReplace' str
= if j == 0
then ("",drop len str,True)
else failed
where failed = case drop (j-1) str of
[] -> (str,"",False)
(c:_) -> (take sk str, drop sk str, False)
where md = j - table ! ord c
sk = if md > 0
then md
else 1

j = srch rsrch (reverse \$ take len str) len
where srch "" "" _ = 0
srch _ "" l = l
srch (s:str) (s':str') l
| s == s' = srch str str' (l-1)
| otherwise = l

Greetings, Bane.

>From: "Branimir Maksimovic" <bmaxa at hotmail.com>
>To: bmaxa at hotmail.com, daniel.is.fischer at web.de
>Date: Thu, 15 Dec 2005 01:39:57 +0000
>
>
>
>
>>From: "Branimir Maksimovic" <bmaxa at hotmail.com>
>>To: daniel.is.fischer at web.de
>>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>
>>>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/
>

_________________________________________________________________
Don't just search. Find. Check out the new MSN Search!
http://search.msn.click-url.com/go/onm00200636ave/direct/01/

```