Согласно стандарту C ++ 03 ISO, §25.1.9 / 3, сложность std::search равна
Сложность: Максимум (последний1 - первый1) * (последний2 - первый2) приложения соответствующего предиката
Это единственное требование к реализации этого алгоритма.Спецификация ISO не определяет, какой алгоритм должен использоваться здесь, и полностью зависит от реализации.Эти временные границы позволяют использовать наивный алгоритм поиска последовательности, Кнут-Моррис-Пратт , Бойер-Мур и Рабин-Карп .Чтобы узнать, какая из них используется, вам, вероятно, следует найти документацию для той версии стандартной библиотеки, которую вы используете.Тем не менее, вы не можете рассчитывать на то, что портативность.Я предполагаю, что большинство реализаций просто используют алгоритм наивного сопоставления, так как наихудший случай обычно не возникает на практике.
Надеюсь, это поможет!