什么是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函数定位s2指向的字符串中字符序列(不包括终止空字符)的s1指向的字符串中的第一个匹配项.

返回

strstr函数返回指向所定位字符串的指针,如果找不到该字符串,则返回空指针.如果s2指向长度为零的字符串,则该函数返回s1.

所以复杂性没有具体说明.据我所知,允许实现使用任何这些算法.