Does STL use Boyer-Moore?

BiK · Post by **BiK** » Mon Oct 11, 2004 7:06 pm

I have recently wondered whether the function for finding a substring of a string is efficiently implemented in STL? In other words, is one of the linear algorithms (Boyer-Moore, KMP or something else) used? Would somebody of you know?

Thanks

makbet · Post by **makbet** » Mon Oct 11, 2004 11:21 pm

I remember trying to solve this problem with STL on some Russian contest (acm.timus.ru or acm.sgu.ru), and I got time limit exceeded. I think all I found about the topic was that the average complexity of their algorithm is linear. So probably the worst case is not linear. I'm not sure though.

marian · Post by **marian** » Sun Oct 24, 2004 11:59 pm

AFAIK, STL implementation included in gcc, doesn't use any sophisticated search algorithm. You can still check it out yourself in /usr/include/c++/ if you have it installed.