Поиск подстроки в строке
В данном обзоре мне хотелось бы рассмотреть наиболее известные алгоритмы поиска. На самом деле их гораздо больше, однако многие мне показались уж слишком неоптимальными.
Описание алгоритмов взято из статьи 'EXACT STRING MATCHING ALGORITHMS' авторов Christian Charras - Thierry Lecroq.
Оригинал статьи находится на http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Данные алгоритмы ищут все вхождения подстроки в текст.
Обозначения и определения
Искомый образец - строка x = x [ 0 ... m - 1 ]; его длина m.
Текст - строка y = y [ 0 ... n - 1 ]; его длина n.
Алфавит ( множество символов, из которых составлены текст и образец ) - S, в нем s символов.
Слово u - префикс cлова w, если существует слово v : w = uv.
Слово v - суффикс cлова w, если существует слово u : w = uv.
Слово z - подстрока слова w, если существуют u и v : w = uzv.
Слово u - период слова w, если w - префикс слова uk для целого k. Наименьший период мы далее и будем называть периодом и обозначать per(w).
Cлово w длины l - периодичное, если длина per(w) <= l/2, в противном случае оно непериодичное.
Слово называется фундаментальным, если оно не может быть записано в виде степени другого слова, то есть не существует z : w = zl.
Cлово z - граница слова w, если существуют u и w : w = uz = zv, z - одновременно префикс и суффикс w.
Обращение слова w длины l обозначается wR - зеркальный образ w; wR = w[ l - 1 ]w[ l - 2 ] ... w[ 1 ]w[ 0 ].
В программах будут использованы следующие функции и константы:
константа ASIZE - размер алфавита,
константа WORD - размер компьютерного слова в битах, обычно 16
константа XSIZE - размер образца,
функция ERROR сообщает об ошибке,
функции MIN / MAX - минимум / максимум,
функция OUTPUT возвращает позицию начала совпадения относительно начала текста.
В остальном же все, я надеюсь, следует стандарту Aнси - Си.
Для практических целей рекомендуются в первую очередь улучшения Боуера-Мура:
Быстрый поиск, Оптимальное несовпадение, Максимальный сдвиг и Турбо-БМ,
а также несколько специфичные Турбо-обращение сегмента и Сдвиг-Или.
Алгоритмы
Алгоритм |
Время на предварительную обработку |
Среднее время поиска |
Худшее время поиска |
Требования к памяти |
Оптимальность |
Нет |
2*n |
O(n*m) |
Нет |
Mалые трудозатраты на программу |
|
O(s+m) |
O(n) |
O(n) |
O(s*m) |
- |
|
Нет |
O(n+m) |
O(n*m) |
Нет |
- |
|
O(s+m) |
O(n) |
O(n) |
- |
Хорош, если длина |
|
O(m) |
O(n+m) |
O(n+m) |
O(m) |
- |
|
O(m) |
O(n+m) |
O(n+m) |
O(m) |
- |
|
O(1) |
чуть меньше линейного |
O(n*m) |
O(1) |
Время и место для |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Чрезвычайно хорош для большого, по сравнению с образцом, размера алфавита. Лучшее время: O(n/m) ! |
|
O(m+s) |
O(n+m) |
2*n |
O(m+s) |
Улучшение предыдущего алгоритма. |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Легок в реализации |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска |
|
O ( m ) |
O(n(logsm)/m) |
O(n*m) |
O ( m ) |
- |
|
O ( m ) |
O(n(logsm)/m) |
2n |
O ( m ) |
маленький алфавит и длинный образец |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска |
