c++ - STL字符串比较方法与手动编写的方法之间存在巨大的时间差异

Question

程序的任务是检查字符串 s2 是否是另一个字符串 (s1 + s1) 的子字符串，给定 s1 和 s2 的长度相等。

例如:[s1, s2] = ["abc", "bca"] 应返回 true 而 [s1, s2] = ["abc", "bac"] 应返回 false。

两个字符串的长度限制都是10^5。

使用 (s1+s1).find(s2) == string::npos 大约需要 0.1 秒即可完成。

我用一种简单的方法实现了它，复杂度为 O(n*m) 并且花了 30 秒!!

s1 = s1 + s1;
bool f = 0;
for(int i = 0;i < s1.size() - s2.size() + 1;i++){
    f = 1;
    for(int j = 0;j < s2.size();j++){
        if(s1[i+j] != s2[j]){
            f = 0;
            break;
        }
    }
    if(f)
        break;
}
//the answer is f

所以我认为 C++ 使用了像 KMP 这样的算法，但我发现它是实现定义的，而 GNU gcc 只使用了朴素的方法并做了一些改进。

但这还不是最大的问题。当我用 s1.compare(i, s2.size(), s2) 替换内部循环时，它花费的时间与 STL 查找方法大约相同 0.1 秒。

bool f = 0;
for(int i = 0;i < s1.size() - s2.size() + 1;i++){
    if(s1.compare(i, s2.size(), s2) == 0){
        f = 1;
        break;
    }

}

那么 C++ 编译器是否以不同的方式实现比较？

C++ 编译器使用的方法在使用相同复杂度的情况下超越朴素方法 300 倍的改进是什么？

注意:我对前面代码使用的测试是

s1 = "ab"*50000 + "ca"

s2 = "ab"*50000 + "ac"

Answer 1

正如上面评论中的回答。

程序在未优化的调试版本中运行，切换到 Release模式后时间减少到仅 3 秒。

剩下的区别可能是因为运行时库使用了一些方法，比如 memcmp，与逐个循环和比较字符相比，该方法经过了大量优化。