我知道有快速的字符串搜索算法，比如 Boyer–Moore和 Knuth–Morris–Pratt ，复杂度为 O(n+m)，而简单的解决方案为 O(n*m)。
那么最流行的工具链(gcc 和 Visual Studio)的 strstr() 的实现是使用这些快速的 O(n) 算法，还是使用简单的解决方案？
最佳答案
GCC 的运行时库使用双向算法，它在最坏的情况下执行 2n-m 文本字符比较。搜索阶段的复杂度为 O(n)，但需要额外的预处理阶段，复杂度为 O(m)。您可以在 http://www-igm.univ-mlv.fr/~lecroq/string/node26.html 上找到详细信息关于算法。
AFAIK MSVC 运行时以最简单的方式执行 strstr，复杂度为 O(n*m)。但是蛮力不需要额外的内存空间，所以它永远不会引发错误的分配异常。 KMP 需要 O(m) 额外空间，Two-Way 需要常数额外空间。
GCC 所做的听起来就像使用 FFT 来计算乘法。在纸上看起来非常快，但在实践中真的很慢。 MSVC 将在可用时在 strstr 中使用 SIMD 指令，因此在大多数情况下速度更快。如果我要编写自己的库，我会选择使用 SIMD 的蛮力方法。
关于c - strstr() 在 gcc 和 VS 中的实现是否具有线性复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22804988/