Search algorithms in __gnu_cxx::

Dhruv Matani dhruvbird@gmail.com
Fri Sep 15 07:24:00 GMT 2006


> The algorithm that I have implemented is a slight variant,
> and is also sometimes called the Turbo Boyer Moore(a simpler version
> of Boyer Moore,

Sorry, it's not called anything, but it's simpler to implement this
way. Many text editors, etc.... probably implement it this way. I
wrote this name by mistake since I was in the process of reading about
it :D However, the complexity does in fact remain the same.

If you see the example on this page:
http://www-igm.univ-mlv.fr/~lecroq/string/examples/exp14.html

The only place that this algorithm differs from the one shown is at
step 4, where instead of making a jump of size 7, it will make 2
jumps, one of size 1 and the next of size 7. In some cases it's
better, and in others it is worse.


Regards,
-Dhruv.




-- 
   -Dhruv Matani.
http://www.geocities.com/dhruvbird/

"Life is wasted on the living"
  - Zaphod Beeblebrox the Fourth.



More information about the Libstdc++ mailing list