Что такое временная сложность, пространственная сложность и алгоритм для функции strstr () в C ++?
Мне было интересно узнать стоимость использования стандартной функции strstr () по умолчанию в C ++. Какова сложность времени и пространства? Какой алгоритм он использует?
У нас есть другие алгоритмы с наихудшим временем и пространственной сложностью:
Пусть n = длина строки, m = длина шаблона
- Алгоритм Кнута-Морриса-Пратта: Время = O (n + m), Пространство = O (m)
- Алгоритм Рабина-Карпа: Время = O (n * m), Пространство = O (p) (p = p шаблонов общей длины m)
- Алгоритм Бойера-Мура: время = 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.
Так что сложность не уточняется. Насколько я могу судить, реализация может использовать любой из этих алгоритмов.
Другие решения
Ну, это полностью зависит от окружающей среды.
Среда выполнения AFAIK MSVC делает strstr самым наивным способом, в сложности O (n * m). Но грубой силе не требуется дополнительное пространство памяти, поэтому она никогда не вызывает исключение некорректного выделения памяти. KMP требуется O (м) дополнительного пространства, а для двухстороннего — постоянное дополнительное пространство.
То, что делает GCC, звучит так же, как использование FFT для вычисления умножения. На бумаге выглядит очень быстро, но на практике очень медленно. MSVC будет использовать инструкции SIMD в strstr, когда они будут доступны, поэтому в большинстве случаев это даже быстрее. Я выберу метод грубой силы с SIMD, если собираюсь написать свою собственную библиотеку.