在std::search中使用什么算法？

Question

有许多字符串匹配算法可用于在大文本中查找模式(字符串)，如Boyer-Moore，Aho-Corasick等。

在C++中使用哪种字符串匹配算法来实现std::search函数？

Answer 1

根据ISO标准，§25.1.9/3，std::search的复杂性是

复杂度:对应谓词的最多(last1 - first1) * (last2 - first2)应用

这是实现此算法的唯一要求。ISO规范没有指定在这里应该使用哪种算法，而且它完全依赖于实现。这些时间限制允许使用朴素的序列搜索算法、Knuth-Morris-Pratt、Boyer-Moore和Rabin-Karp。要了解正在使用的是哪个版本的标准库，您可能应该调出您正在使用的标准库的文档。也就是说，你不能指望它是可移植的。我的猜测是，大多数实现只使用朴素的匹配算法，因为在实践中通常不会出现最坏的情况。

希望这能有所帮助！