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