In you are interested, here is a template implementation of the Boyer-Moore Fast Find algorithm. It can find substrings in text much faster than a plain scan.

http://svn.dsource.org/svn/projects/build/trunk/Source/util/BMscanner.d

You can delete the line "private import util.bmscanner_bn;" if you aren't interested in the Build utility's automatic build numbering facility. And you might have to change the module's package name to suit your own directory structure.

-- 
Derek Parnell
Melbourne, Australia
http://www.dsource.org/projects/build/ v1.19 released 04/Apr/2005
http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage
6/04/2005 5:11:50 PM

Nice work! Would be interesting to check under which conditions this algorithm is faster than plain scan. For short strings, the overhead will probably outweigh the speedup. (Especially considering that searching one fixed byte in a block of data can be done very efficiently in assembler.)

Would certainly be interesting to do some benchmarking.

Derek Parnell schrieb:
> In you are interested, here is a template implementation of the Boyer-Moore
> Fast Find algorithm. It can find substrings in text much faster than a
> plain scan.
> 
> http://svn.dsource.org/svn/projects/build/trunk/Source/util/BMscanner.d
> 
> You can delete the line "private import util.bmscanner_bn;" if you aren't
> interested in the Build utility's automatic build numbering facility. And
> you might have to change the module's package name to suit your own
> directory structure.
>