[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>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: Mon, 12 Dec 2005 16:15:46 +0100
>
>Earlier today:
> > Sorry, but
> > Prelude SearchRep> searchReplace "abaaba" "##" "abababaaba"
> > "abababaaba"
> >
> > I haven't analyzed the algorithm, so I don't know why exactly this 
>fails.
> > I'll take a look sometime soon.
> >
>
>I found the problem (one at least).
>Say the pattern to be replaced begins with 'a' and we have a sufficiently 
>long
>match with the pattern starting at the first 'a' in the String. Upon
>encountering the second 'a', while the first pattern still matches, you 
>start
>pushing onto the rollback-stack. But that isn't inspected anymore, so if 
>the
>actual occurence of the pattern starts at the third (or fourth, n-th)
>occurence of 'a' and that is already pushed onto the rollback, you miss it.
>
>let src = concat (replicate n "abc") ++ "d"
>let str = concat (replicate (n+k) "abc") ++ "d"
>then
>searchReplace src "Success!" str
>will work correctly iff k is congruent to 0 or 1 modulo (n+1).
>

Oh, yes this seems the problem for searchr :(
I have to look for efficient way in order to circumvent repeated searches.
But since your KMP is fastest of all now, I am considering if there
is any point now to correct this.

And searchr ugly version that I've posted has a bug (not present in MyBane 
pretty
version) .
should be :
else if sr'/=x

Greetings, Bane.

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