:: алгоритмы и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Поиск. Строки и последовательности » Точный подстроки в строке
  Точный поиск подстроки в строке
     В данном обзоре мне хотелось бы рассмотреть наиболее известные алгоритмы поиска. На самом деле их гораздо больше, однако многие мне показались уж слишком неоптимальными.

     Описание алгоритмов я перевел, взяв статью 'EXACT STRING MATCHING ALGORITHMS' авторов Christian Charras - Thierry Lecroq.

     Оригинал статьи находится на 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(n*m)
O(1)
Время и место для предобработки - константа.
O(m+s)
O(n+m)
O(n*m)
O(m+s)
Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита.
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)
Очень быстрый алгоритм для обычных текстов и поиска. Большой объем предварительных вычислений.