S.find() из библиотеки string

Стандарт не накладывает никаких ограничений на сложность std::string::find, поэтому надо смотреть на конкретные имплементации стандартной библиотеки. В реализации библиотеки для gcc, например, используется наивный алгоритм со сложностью O(длина-строки * длина-образца) (см. basic_string<...>::find, char_traits<char>::compare).