C++ 中 strstr() 函数的时间复杂度、Space 复杂度和算法是什么？
What is the Time Complexity, Space complexity and Algorithm for strstr() function in C++?
我很好奇在 C++ 中使用默认的老式 strstr() 函数的成本。它的时间和 Space 复杂度是多少？它使用哪种算法？
我们还有其他算法具有以下最坏情况时间和 Space 复杂度：
设 n = 字符串长度，m = 模式长度
- Knuth-Morris-Pratt 算法：时间 = O(n+m)，Space = O(m)
- Rabin-Karp 算法：时间 = O(n*m)，Space = O(p)（p = p 组合长度 m 的模式）
- Boyer-Moore 算法：时间 = O(n*m)，Space = O(S)（S = 字符集的大小）
就时间和 Space 复杂性而言，strstr() 无论如何都比上述算法更好？
在 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.
所以复杂度未指定。据我所知，一个实现可以使用任何这些算法。
我很好奇在 C++ 中使用默认的老式 strstr() 函数的成本。它的时间和 Space 复杂度是多少？它使用哪种算法？ 我们还有其他算法具有以下最坏情况时间和 Space 复杂度： 设 n = 字符串长度，m = 模式长度
- Knuth-Morris-Pratt 算法：时间 = O(n+m)，Space = O(m)
- Rabin-Karp 算法：时间 = O(n*m)，Space = O(p)（p = p 组合长度 m 的模式）
- Boyer-Moore 算法：时间 = O(n*m)，Space = O(S)（S = 字符集的大小） 就时间和 Space 复杂性而言，strstr() 无论如何都比上述算法更好？
在 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.
所以复杂度未指定。据我所知，一个实现可以使用任何这些算法。