www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Lazy KMP range

reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Jun 15 2012
next sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Jun 15 2012
prev sibling next sibling parent reply "Roman D. Boiko" <rb d-coding.com> writes:
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.
Jun 15 2012
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
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
Jun 15 2012
prev sibling next sibling parent "Roman D. Boiko" <rb d-coding.com> writes:
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 :)
Jun 15 2012
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Jun 15 2012