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.
I've corrected this with adjusting rollback position. if rollBack is null
then
search for rollback starts at second character if not starts at same as
searhed
character because I skip what was searched. That's all.
Though I'm not so sure now when I read this.
So the question is, can we find a cheap test to decide whether to use KMP
or
Bulat's version?
In real world situation your KMP will always be fastest on average.
I like that we are not using C arrays as then we have advantage
of lazyness and save on memory usage. C++ program will be faster
on shorter strings but on this large strings will loose due memory
latency. and with your test, both programs are very fast.
Greetings, Bane.
_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE!
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
