C++中string::rfind方法的时间复杂度是多少？是否为反转后调用find？

• 关于实现逻辑：你的理解不对，C标准并没有要求string::rfind必须通过反转字符串再调用find来实现。主流编译器的标准库（比如GCC的libstdc、Clang的libc++）都是直接从字符串末尾开始向前逐个匹配目标子串，不会额外做反转操作。

• 时间复杂度：string::rfind的时间复杂度是O(n*m)，其中n是原字符串的长度，m是要查找的子串长度。最坏情况下，需要从后往前遍历每个可能的起始位置，每个位置都要和子串做逐字符比较，每次比较耗时O(m)，整体就是O(nm)。
  哪怕真按你说的反转+find的方式实现，find本身最坏情况也是O(nm)，加上反转的O(n)，整体复杂度还是O(n*m)，不是O(n)。只有当查找单个字符（m=1）时，时间复杂度才会降到O(n)。

内容的提问来源于stack exchange，提问作者Sababoni