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 reply 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
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
prev 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
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 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