What algorithm is used in std::search?

Question

There are many string matching algorithms can be used to find a pattern (string) in a big text, like Boyer-Moore, Aho-Corasick, etc.

Which string matching algorithm is applied to implement std::search function in C++ ?

Answer 1

According to the C++03 ISO standard, §25.1.9/3, the complexity of std::search is

Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate

This is the only requirement on the implementation of this algorithm. The ISO spec does not specify which algorithm should be used here, and it's completely implementation-dependent. These time bounds permit the use of the naive sequence-searching algorithm, Knuth-Morris-Pratt, Boyer-Moore, and Rabin-Karp. To know which one is being used, you should probably pull up the documentation for whichever version of the standard library that you're using. That said, you can't count on that being portable. My guess is that most implementations just use the naive matching algorithm, since the worst case typically doesn't arise in practice.

Hope this helps!