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=p组合长度为m的模式）
3. Boyer-Moore算法：时间=O（n*m），空间=O（S）（S=字符集大小）在时间和空间复杂性方面，strstr（）在任何方面都比上面提到的算法好

Answer 1

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

简介

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

说明

strstr函数定位字符序列中s1指向的字符串中的第一个出现（不包括终止空字符）。

退货

strstr函数返回一个指向已定位字符串的指针，如果找不到字符串，则返回一个空指针。如果s2指向长度为零的字符串，函数返回s1。

因此，其复杂性尚未明确。据我所知，一个实现可以使用这些算法中的任何一个。