Окулов С.М. Алгоритмы обработки строк

Монография, М.: Бином. Лаборатория знаний, 2009. - 255 с.
В издании даны основы предварительного анализа строк, приведены классические алгоритмы решения задач обработки строк, описаны алгоритмы построения дерева суффиксов, рассмотрены задачи вычисления расстояния между строками, даны алгоритмы приближенного поиска подстрок. Оглавление.
Предисловие.
Строки.
Основные понятия.
Методы предварительного анализа строк.
Классические алгоритмы решения задач обработки строк.
Алгоритм Д.Кнута–Дж. Морриса–В.Пратта.
Алгоритм Р.Бойера–Дж.Мура.
Алгоритм Р.Карпа–М.Рабина.
Алгоритм Shift-And.
Использование элементов теории автоматов в решении задач обработки строк.
Алгоритм М.Крочемора.
Алгоритм М.Мейна–Р.Лоренца.
Деревья суффиксов.
Основные понятия. Простые алгоритмы построения дерева суффиксов.
Алгоритм Э.Укконена.
Алгоритм Е.Мак-Крейга.
Суффиксные массивы.
Алгоритм А.Ахо–М.Корасик.
Вычисление расстояния между строками.
Основной алгоритм.
Алгоритм Э.Укконена–Ю.Майерса.
Задача о наибольшей общей подпоследовательности двух строк.
Алгоритмы приближенного поиска подстрок.
Простой алгоритм.
Алгоритм С.Ву–Ю.Менбера.
Задача о k-несовпадениях.
Алгоритм Ю.Майерса.
Вместо заключения.
Приложения.