c++ - C++ 中 strstr() 函数的时间复杂度、空间复杂度和算法是什么？

Question

我很好奇在 C++ 中使用默认的老式 strstr() 函数的成本。它的时间和空间复杂度是多少？它使用哪种算法？我们还有其他具有以下最坏情况时间和空间复杂度的算法:设 n = 字符串长度，m = 模式长度

1. Knuth-Morris-Pratt 算法:时间 = O(n+m)，空间 = O(m)
2. Rabin-Karp 算法:时间 = O(n*m)，空间 = O(p)(p = 组合长度 m 的 p 模式)
3. Boyer-Moore 算法:时间 = O(n*m)，空间 = O(S)(S = 字符集的大小)就时间和空间复杂性而言，strstr() 在任何方面都优于上述算法？

Answer 1

在 C 标准中它只是说，在 §7.24.5.7 中:

Synopsis

 #include <string.h>
 char *strstr(const char *s1, const char *s2);

Description

The strstr function locates the first occurrence in the string pointed to by s1 of the sequence of characters (excluding the terminating null character) in the string pointed to by s2.

Returns

The strstr function returns a pointer to the located string, or a null pointer if the string is not found. If s2 points to a string with zero length, the function returns s1.

所以复杂度是不确定的。据我所知，一个实现可以使用任何这些算法。