C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？

C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？

在C标准中，仅在§7.24.5.7中说：

概要

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

描述

strstr函数在s1指向的字符串中找到s2指向的字符串中的字符序列（不包括终止空字符）的第一个匹配项。

退货

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

因此，复杂度未指定。据我所知，允许实现使用任何这些算法。