strstr（）在gcc和VS中的实现是否具有线性复杂性？
我知道有快速的字符串搜索算法，如Boyer-Moore和Knuth-Morris-Pratt ，它们具有O（n + m）复杂度，而普通解决方案将是O（n * m）。
那么最流行的工具链（gcc和Visual Studio）的strstr（）的实现是使用这些快速的O（n）算法，还是使用简单的解决方案？
GCC的运行时库使用Two-Way Algorithm ，在最坏的情况下执行2n-m文本字符比较。 它在搜索阶段是O（n）复杂度，但它需要额外的预处理阶段，即O（m）复杂度。 您可以在http://www-igm.univ-mlv.fr/~lecroq/string/node26.html上找到有关该算法的详细信息。
AFAIK MSVC运行时以最简单的方式执行strstr ，O（n * m）复杂度。 但是暴力破解不需要额外的内存空间，所以它永远不会引发错误的allocexception。 KMP需要O（m）额外空间，而双向需要恒定的额外空间。
GCC正在做什么听起来就像使用FFT来计算乘法。 在纸上看起来非常快，但在练习中确实很慢。 当MSVC strstr时，它们将在strstr使用SIMD指令，因此在大多数情况下它甚至更快。 如果我要编写自己的库，我将选择使用SIMD的powershell方法。