STL字符串比较方法和手动编写的方法之间存在巨大的时间差

两条弦的长度极限为10^5。

使用 (s1+s1).find(s2) == string::npos 花了大约。还剩1秒。

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查找方法花费的时间大致相同。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倍?

:

s2=“ab”*50000+“ac”