A lazy Knuth-Morris-Pratt that works on a Input Range:
http://ideone.com/dUs5B

Do you have suggestions for improvements of the code? Maybe do I have to turn it into a Forward Range if the first range is a Forward one? Is something similar to this useful for Phobos?

Bye and thank you,
bearophile

On 15.06.2012 23:03, bearophile wrote:
> A lazy Knuth-Morris-Pratt that works on a Input Range:
> http://ideone.com/dUs5B
>
> Do you have suggestions for improvements of the code? Maybe do I have to
> turn it into a Forward Range if the first range is a Forward one? Is
> something similar to this useful for Phobos?
>

Yes, definitely just decouple table preparation and searching range itself.  It's common to use KMP and its ilk to do a lot of series of searches for the same needle.

> Bye and thank you,
> bearophile


-- 
Dmitry Olshansky

On Friday, 15 June 2012 at 19:03:56 UTC, bearophile wrote:
> A lazy Knuth-Morris-Pratt that works on a Input Range:
> http://ideone.com/dUs5B
>
> Do you have suggestions for improvements of the code? Maybe do I have to turn it into a Forward Range if the first range is a Forward one? Is something similar to this useful for Phobos?
>
> Bye and thank you,
> bearophile

Pay attention to "Licensed under the PSF License" for your source implementation. You will not be able to include it into Phobos unless implementation details that you borrowed from Python implementation can be found elsewhere under terms that allow applying Boost license.

On Friday, 15 June 2012 at 19:41:35 UTC, Roman D. Boiko wrote:
> Pay attention to "Licensed under the PSF License" for your source implementation. You will not be able to include it into Phobos unless implementation details that you borrowed from Python implementation can be found elsewhere under terms that allow applying Boost license.

You might also ask the author for permission to change license, provided that that person didn't get it elsewhere under some other terms :)

On 15.06.2012 23:41, Roman D. Boiko wrote:
> On Friday, 15 June 2012 at 19:03:56 UTC, bearophile wrote:
>> A lazy Knuth-Morris-Pratt that works on a Input Range:
>> http://ideone.com/dUs5B
>>
>> Do you have suggestions for improvements of the code? Maybe do I have
>> to turn it into a Forward Range if the first range is a Forward one?
>> Is something similar to this useful for Phobos?
>>
>> Bye and thank you,
>> bearophile
>
> Pay attention to "Licensed under the PSF License" for your source
> implementation. You will not be able to include it into Phobos unless
> implementation details that you borrowed from Python implementation can
> be found elsewhere under terms that allow applying Boost license.

Bearophile if license is a problem you might try your hand on these:

http://www-igm.univ-mlv.fr/~lecroq/string/

A lot of stuff ;)
-- 
Dmitry Olshansky

Dmitry Olshansky:

> Yes, definitely just decouple table preparation and searching range itself.  It's common to use KMP and its ilk to do a lot of series of searches for the same needle.

OK.

Regarding the license, this is a translation from another language of a basic algorithm. I don't think the original license applies.
And if it applies, the author is Eppstein (http://en.wikipedia.org/wiki/David_Eppstein ) that I know well. For a translation of such small amount of code he will probably accept a Boost re-licensing :-)

Bye,
bearophile