[Haskell-cafe] Substring replacements

[Branimir Maksimovic]

>From: Daniel Fischer <daniel.is.fischer at web.de>
>To: "Branimir Maksimovic" <bmaxa at hotmail.com>
>CC: Haskell-Cafe at 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/