strstr() 在 gcc 和 VS 中的实现是否具有线性复杂度？

Question

我知道有一些快速的字符串搜索算法，比如Boyer–Moore和Knuth–Morris–Pratt，它们的复杂度为 O(n+m)，而简单的解决方案是 O(n*m)。

那么，最流行的工具链（gcc 和 Visual Studio）的 strstr() 实现是使用这些快速 O(n) 算法，还是使用简单的解决方案？

Answer 1

GCC 的运行时库使用Two-Way Algorithm它在最坏的情况下执行 2n-m 文本字符比较。搜索阶段的复杂度为 O(n)，但需要额外的预处理阶段，复杂度为 O(m)。您可以在http://www-igm.univ-mlv.fr/~lecroq/string/node26.html上找到有关该算法的详细信息。

据我所知，MSVC 运行时是以strstr最简单的方式执行的，复杂度为 O(n*m)。但暴力破解不需要额外的内存空间，因此它永远不会引发错误的分配异常。KMP需要O(m)的额外空间，而Two-Way需要恒定的额外空间。

GCC 正在做的事情听起来就像使用 FFT 来计算乘法一样。在纸面上看起来非常快，但在实践中却很慢。strstrMSVC 将在可用时使用 SIMD 指令，因此在大多数情况下速度更快。如果我要编写自己的库，我会选择使用 SIMD 的强力方法。