Far*_*zam 17 c++ string algorithm substring time-complexity
为什么c ++的实现string::find()不使用KMP算法(并且不运行O(N + M))并运行O(N * M)？这是在C++ 0x中纠正的吗？如果当前查找的复杂性不是O(N * M),那是什么？
PS:对不起,我的意思是 O(N * M)
那么在gcc中实现了什么算法？是KMP吗？如果没有,为什么？我测试了它,运行时间表明它运行了string::find()
Mik*_*our 29
为什么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).因此,通过选择具有更好的最坏情况复杂度的算法,您可能会使更典型的情况更慢.
仅供参考，gcc/libstdc++ 和 llvm/libcxx 中的 string::find 非常慢。我非常显着地改进了它们（在某些情况下提高了约 20 倍）。您可能想要检查新的实现：
GCC：PR66414 优化 std::string::find https://github.com/gcc-mirror/gcc/commit/fc7ebc4b8d9ad7e2891b7f72152e8a2b7543cd65
LLVM：https : //reviews.llvm.org/D27068
新算法更简单，并使用了 memchr 和 memcmp 的手工优化汇编函数。
你从哪里得到的印象是std::string::substr()不使用线性算法？事实上,我甚至无法想象如何以一种具有所引用复杂性的方式实现.此外,没有太多的算法涉及:你是否认为这个函数做了别的事情呢？std::string::substr()只需从第一个参数开始创建一个新字符串,并使用第二个参数指定的字符数或字符串末尾的字符.
您可能指的是std::string::find()哪个没有任何复杂性要求或者std::search()确实允许进行O(n*m)比较.然而,这是给予实施者自由选择具有最佳理论复杂度的算法与不需要额外存储器的算法之间的选择.由于除非特别要求,否则通常不希望分配任意数量的内存,这似乎是合理的做法.