3
Алгоритм
Время выполнения (мс)
Длина ?10
Длина ?100
Длина ?250
Послед. Поиск
15
93
234
Алгоритм Рабина
63
КМП
5
30
50
БМ
31
32
Примечания
Алгоритмы, основанные на алгоритме последовательного поиска
Малые трудозатраты на программу, малая эффективность
Алгоритм Кнута-Морриса-Пратта
Универсальный алгоритм, если неизвестна длина образца
Алгоритм Бойера-Мура
Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита.
Время работы (мс) при длине строки ?250
Затраты памяти
нет
O(m)
O(m+s)
Худшее время поиска
O((m-n+1)*n+1)
O(n+m)
O(n*m)
Среднее время поиска
O((m-n+1)*n+1)/2
Время на пред. обработку
Алгоритм прямого поиска