c++ - 使用 C++ 在另一个字符串中找到给定开始和结束位置的子字符串的更快方法？

Question

任务是在给定“haystack”的开始位置和结束位置的情况下，在另一个字符串(haystack)中找到一个子串(needle)。开始和结束位置遵循STL约定，即结束位置是感兴趣范围之后字符的位置。

例如:在“0123456789”中查找beg_pos=0和end_pos=8的“567”应该返回5，而查找““0123456789”中 beg_pos=0 和 end_pos=4 的 567"应该返回 -1。

我可以想象两个简单的实现:

• 方法一:使用size_t pos = haystack.find(needle, beg_pos);获取子串位置，然后比较返回值pos 和 end_pos 如果找到。在最坏的情况下，find 函数将一直查找到字符串 haystack 的末尾，但是在 end_pos 之后的搜索是不必要的。如果 haystack 很长，性能可能会很差。
• 方法二:使用size_t pos = haystack.substr(beg_pos, end_pos-beg_pos).find(needle);找到位置，然后返回 pos+beg_pos 如果找到。这种方法避免了在end_pos之后进行不必要的搜索的问题，但是它需要分配一个新的临时字符串，这也可能存在性能问题。

我想知道是否有更快的方法来完成任务。

Answer 1

在 C++17 中我们有 std::string_view可以用指针和大小构造。这将允许您获得字符串的只读片段，其中不会复制任何内容。然后您可以使用 std::string_view::find查找子字符串是否存在于该切片中。看起来像

std::string haystack = "lots of stuff";
std::string needle = "something";
std::string_view slice(haystack.c_str() + start, end - start); // use end - start to get size of the slice
auto pos = slice.find(needle);
if (pos == std::string::npos)
    return -1;
else
    return pos; // or pos + start if you need the index from the start and not just in the slice.