[Haskell-cafe] Substring replacements

[Daniel Fischer]

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