0

I wonder which algorithm is used for matching a pattern against a string in the standard library. A suffix tree would be the best choice if one has got more search to perform within the same string.

Is that the data structure behind std::string::find() or a one-shot algorithm like Knuth-Morris-Pratt algorithm is used?

Nisba
  • 3,210
  • 2
  • 27
  • 46
  • Such information is just an implementation detail. Only the maximum complexity of the functions, are imposed by the C++ standard. There are plenty of open source implementations of C++ compilers, and you can check how it's done there. – Algirdas Preidžius Mar 12 '18 at 17:46
  • There is an abyssal difference between the KMP or similar and a data structure like suffix tree. It can really completely change the game – Nisba Mar 12 '18 at 17:49
  • As I already mentioned - only the complexity is imposed on `std` functions, by the C++ standard. Such things as algorithms used is just an implementation detail, and every vendor can implement internal logic however they want. – Algirdas Preidžius Mar 12 '18 at 17:52
  • 1
    From what I've seen, `string::find` is most often implemented as a brute-force search. You might want to consider using `std:search` instead--it supports specifying a Boyer-Moore or Boyer-Moore-Horspool search. Out of the box it doesn't include KMP or suffix tree searching, but it does specify an interface so you could have `std::search` use them as well if you wanted. – Jerry Coffin Mar 12 '18 at 18:01

0 Answers0