This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Search algorithms in __gnu_cxx::


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.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]