OJ Board

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

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.

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.