为什么 c++ 实现的 string::find() 不使用 KMP algorithm (并且不在 O(N + M) 中运行)并在 O(N * M) 中运行？这在 C++0x 中是否得到纠正？
如果当前查找的复杂度不是O(N * M)，那是什么？
那么 gcc 中实现了什么算法呢？是KMP吗？如果不是，为什么？
我已经测试过了，运行时间显示它运行在 O(N * M)
最佳答案
Why the c++'s implemented string::substr() doesn't use the KMP algorithm (and doesn't run in O(N + M)) and runs in O(N * M)?
我假设您的意思是 find()，而不是 substr()，它不需要搜索并且应该在线性时间内运行(并且只是因为它必须将结果复制到一个新字符串中)。
C++ 标准没有指定实现细节，仅在某些情况下指定复杂性要求。 std::string 操作的唯一复杂性要求是 size()、max_size()、operator[]、swap()、c_str()和data()都是常数时间。其他任何事情的复杂性取决于实现您正在使用的库的人所做的选择。
选择简单搜索而不是 KMP 之类的最可能的原因是避免需要额外的存储空间。除非要找到的字符串很长，并且要搜索的字符串包含很多部分匹配，否则分配和释放所花费的时间可能会远远超过额外复杂性的成本。
Is that corrected in c++0x?
不，C++11 没有对 std::string 增加任何复杂性要求，当然也没有增加任何强制性的实现细节。
If the complexity of current substr is not O(N * M), what is that?
这是最坏情况的复杂性，当要搜索的字符串包含很多长的部分匹配时。如果字符具有合理均匀的分布，则平均复杂度将更接近 O(N)。因此，通过选择具有更好的最坏情况复杂性的算法，您可能会使更典型的情况变得更慢。
关于C++ string::find 复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8869605/