[Haskell-cafe] Substring replacements
bmaxa at hotmail.com
Mon Dec 12 11:56:19 EST 2005
>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
> > Sorry, but
> > Prelude SearchRep> searchReplace "abaaba" "##" "abababaaba"
> > "abababaaba"
> > I haven't analyzed the algorithm, so I don't know why exactly this
> > 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
>match with the pattern starting at the first 'a' in the String. Upon
>encountering the second 'a', while the first pattern still matches, you
>pushing onto the rollback-stack. But that isn't inspected anymore, so if
>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"
>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
should be :
else if sr'/=x
FREE pop-up blocking with the new MSN Toolbar - get it now!
More information about the Haskell-Cafe