Какова временная сложность, пространственная сложность и алгоритм для функции strstr() в C++?

Мне было любопытно узнать стоимость использования старомодной функции strstr() по умолчанию в C++. Какова его временная и пространственная сложность? Какой алгоритм он использует? У нас есть другие алгоритмы со сложностью времени и пространства ниже наихудшего случая: пусть n = длина строки, m = длина шаблона

  1. Алгоритм Кнута-Морриса-Пратта: Время = O(n+m), Пространство = O(m)
  2. Алгоритм Рабина-Карпа: время = O (n * m), пространство = O (p) (p = p шаблонов общей длины m)
  3. Алгоритм Бойера-Мура: время = O (n * m), пространство = O (S) (S = размер набора символов) В любом случае strstr() лучше, чем вышеупомянутые алгоритмы, с точки зрения сложности времени и пространства?

c++ algorithm string-search
person Prasath Govind    schedule 15.12.2015    source источник
comment
В принципе, не указано. Не очень удовлетворительный ответ, я знаю. У вас есть конкретная реализация, о которой вы хотите узнать?   -  person BoBTFish    schedule 15.12.2015
comment
Я имел в виду конкретную реализацию функции или стандартную библиотеку Си. Например, в Gnu libc, или в MS Visual Studio, или в каком-то другом?   -  person BoBTFish    schedule 15.12.2015
comment
Извините.. У меня нет BoB..   -  person Prasath Govind    schedule 15.12.2015
comment
glibc использует KMP, см. Исходный файл strstr.c, хотя он модифицирован с некоторыми оптимизациями sse2.   -  person Demi-Lune    schedule 13.10.2019

Ответы (1)


arrow_upward
7
arrow_downward

В стандарте C в §7.24.5.7 просто сказано:

Синопсис

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

Описание

Функция strstr находит первое вхождение в строке, на которую указывает s1, последовательности символов (за исключением завершающего нулевого символа) в строке, на которую указывает s2.

Возвращает

Функция strstr возвращает указатель на найденную строку или нулевой указатель, если строка не найдена. Если s2 указывает на строку нулевой длины, функция возвращает s1.

Так что сложность не указана. Насколько я могу судить, реализация может использовать любой из этих алгоритмов.

person Shoe    schedule 15.12.2015