1. 首页
  2. 问题
  3. C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？
小编典典

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

algorithm

我对在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（）在任何方面都优于上述算法？

阅读 1010

收藏
2020-07-28

共1个答案

小编典典

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

概要

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

描述

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

退货

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

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

2020-07-28