C++ string::rfind 时间复杂度

Question

string::rfindC++中方法的时间复杂度是多少？据我了解，rfind 正在反转字符串，然后执行string::find. 我对么？那么它应该是O(n)

Answer 1

不，你不正确。rfind从字符串的后面开始搜索，而不反转字符串。复杂性与转发相同find。

我没有在标准中找到任何需要这样做的内容，但是您可以使用的任何搜索算法find（例如朴素搜索或 Boyer-Moore / Boyer-Moore-Horspool 搜索）也可以用于rfind- 所以我发现它非常重要任何库实现者都不太可能选择效率较低的算法来rfind实现。