Суффиксный массив

Суффиксный массив – это массив, в котором хранятся все суффиксы некоторой строки, отсортированные лексикографически. Эту структуру изобрели Джин Майерс и Уди Манбер. Она используется при обработке текстов, в алгоритмах сжатия данных и некоторых областях библиометрии.

Полиномиальное хеширование

Полиномиальное хеширование – это один из видов хеширования строк. Он может быть использован для вероятностного сравнения строк в некоторых алгоритмах.

Префикс-функция

Префикс-функция – функция, которая определяется с помощью массива для всех префиксов некоторой строки. Этот массив состоит из длин максимальных префиксов данной строки, совпадающих с суффиксами ее подстрок, но не совпадающих с самой подстрокой.

Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута-Морриса-Пратта – это алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от суммы длин строк. Алгоритм был разработан Д. Кнутом и В. Праттом и, независимо от них, Д. Моррисом.

Алгоритм Бойера-Мура

Алгоритм Бойера-Мура – это алгоритм поиска подстроки в строке. Он был разработан Р. Бойером и Дж. Муром в 1977 году. Особенность алгоритма состоит в том, что он эффективно работает на случайном тексте. Если же входные данные «плохие», то сложность алгоритма без учета препроцессинга такая же, как и у тривиального алгоритма.