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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

回答：

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

概要

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

描述

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

退货

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

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

以上是 C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？ 的全部内容， 来源链接： utcz.com/qa/427231.html

回到顶部