Грэхем А. Анализ строк

Классическое пособие для решения задач, встающих при обработке строк. В этой работе рассматриваются задачи анализа строк, возникающие при разработке систем обработки текстовой информации. Не ставятся целью дать точные решения всех возможных задач, а предлагаются детальные обзоры существующих алгоритмов, подходящих для подобных систем.
Термин анализ строк используется здесь в довольно общем смысле и обозначает целый класс задач – таких, как локализация заданных подстрок, выделение длиннейших совпадающих подстрок двух строк, вычисление расстояния между двумя строками и т.д. Прежде всего совсем общо описывается проблема, затем приводятся точные формулировки. Обсуждаются алгоритмы анализа строк, сравниваются их возможности и эффективность. После этого идет описание основных алгоритмов. Алгоритмы:
- Поиск образцов
- Наивный подход
- Кнут-Моррис-Пратт
- Бойер-Мур
- Бойер-Мур-Хорспул
- Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
- Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
- Харрисон
- Карп-Рабин
- Расстояние между строками и самая длинная общая подпоследовательность
- Вагнер-Фишер
- Хиршберг
- Хант-Шиманский
- Машек-Патерсон
- Укконен
- Самая тяжелая общая подпоследовательность
- Нечеткое сопоставление строк
- k несовпадений - Ландау-Вишкин
- k различий - Ландау-Вишкин
- Самая длинная повторяющася подстрока
- Суффиксные деревья