Search algorithms in __gnu_cxx::

Dhruv Matani
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:

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.


   -Dhruv Matani.

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

More information about the Libstdc++ mailing list