C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？ [英] What is the Time Complexity, Space complexity and Algorithm for strstr() function in C++?

问题描述

我对在C ++中使用默认的老式strstr（）函数的成本感到好奇。它的时空复杂度是多少？它使用哪种算法？
我们还有其他最差情况下的时空复杂度算法：
令n =字符串长度，m =模式长度

I was curious about the cost of using the default, old fashioned strstr() function in C++. What is its Time and Space complexity? Which algorithm does it use? We have other algorithms with below Worst Case Time and Space complexity : Let n = length of string, m = length of pattern

1. Knuth-Morris-Pratt算法：时间= O（n + m），空间= O（m）


2. Rabin-Karp算法：时间= O（n * m ），Space = O（p）（p =组合长度为m的p个模式）


3. Boyer-Moore算法：时间= O（n * m），空间= O（S）（ S =字符集的大小）
   就时间和空间复杂度而言，strstr（）优于上述算法吗？

推荐答案

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

In the C standard it just says, in §7.24.5.7:

简介

Synopsis

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

说明

strstr函数可找到s1指向的字符串中第一次出现在s2指向的字符串中的字符序列（不包括
终止空字符）。

Description

The strstr function locates the first occurrence in the string pointed to by s1 of the sequence of characters (excluding the terminating null character) in the string pointed to by s2.

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

The strstr function returns a pointer to the located string, or a null pointer if the string is not found. If s2 points to a string with zero length, the function returns s1.

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

So the complexity is unspecified. As far as I can tell, an implementation is allowed to use any of those algorithms.

这篇关于C ++中strstr（）函数的时间复杂度，空间复杂度和算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！