[Haskell-cafe] Substring replacements
Daniel Fischer
daniel.is.fischer at web.de
Mon Dec 12 10:15:46 EST 2005
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).
Now to fix it, I see two possibilities
1. re-inspect the rollback, which brings you basically to my srchrep
2. introduce a hierarchy of rollback-stacks - but that would be rather
horrible, I think, because you must keep count on which stack you have to
push, how many matching patterns you currently have (and which ones they are)
...
So the question is, can we find a cheap test to decide whether to use KMP or
Bulat's version?
Cheers,
Daniel
More information about the Haskell-Cafe
mailing list