c++ - C++23 中 std::string::contains 的时间复杂度是多少？

Question

但没有运行时要求。是否保证在线性时间内运行？（例如，在实现中使用 KMP 算法）还是二次时间？

我试图在当前的 C++ 标准草案（http://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf）中找到它，但我找不到参考。

score 6 · Accepted Answer

按照最新的草稿，contains是：

相当于：

return basic_string_view<charT, traits>(data(), size()).contains(x);

相当于：return find(x) != npos;

由于相等性测试整数basic_string_view::npos是一个常数时间操作，时间复杂度将是basic_string_view::find：

本小节中的成员函数在最坏的情况下具有 O(size() * str.size()) 的复杂性，尽管实现应该做得更好。

score 0 · Accepted Answer

提案 (P1679 )表明contains相当于find(x) != npos。

在最坏的情况下，复杂度可能是 O(size() * str.size())。如果两个字符串都是已知的，那么最多可以在编译时执行操作，因为两者std::string::contains都是std::string_view::contains方法constexpr。

请注意，目前 (GCC 11) 仅在 libstdc++ 中std::string_view具有功能。constexpr

2 回答 2