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