为什么C ++实现的string :: substr（）不使用KMP算法（也不在O（N + M）中运行）而在O（N * M）中运行？

我假设您的意思是find()，而substr()不是不需要搜索，而是应该在线性时间内运行（并且仅因为它必须将结果复制到新字符串中）。

C
++标准未指定实现细节，仅在某些情况下指定了复杂性要求。上唯一的复杂性要求std::string操作是size()，max_size()，operator[]，swap()，c_str()和data()都是恒定的时间。其他任何事物的复杂性都取决于实现您所使用的库的人的选择。

选择诸如KMP之类的简单搜索的最可能原因是避免需要额外的存储空间。除非要找到的字符串很长，并且要搜索的字符串包含很多部分匹配项，否则分配和释放所花费的时间可能要比额外的复杂性花费更多。

在c ++ 0x中可以纠正吗？

不，C ++ 11不会向中添加任何复杂性要求std::string，当然也不会添加任何强制性的实现细节。

如果当前substr的复杂度不是O（N * M），那是什么？

当要搜索的字符串包含很多长的部分匹配项时，这就是最坏的情况。如果字符具有合理均匀的分布，则平均复杂度将接近O(N)。因此，通过选择具有更好的最坏情况复杂度的算法，可以使更典型的情况变慢得多。