Хотя этот обзор написан относительно давно, он, судя по всему, еще не потерял актуальности. Перечисленные в нем задачи и методы их решения составляют основу интенсивных исследований. Активные эксперименты с суффиксными деревьями привели к резкому снижений требуемой ими памяти, так что они становятся де-факто стандартом в приложениях, связанных с нестрогим поиском в словарях больших объемов. Список примеров легко продолжить.

Конечно, за прошедшие годы проводились многочисленные новые исследования и появились многочисленные новые статьи, не вошедшие в этот обзор. Вместе с тем, конец «периода полураспада» приведенных в нем результатов еще очень далек. Я надеюсь, вы прочтете этот материал с пользой и удовольствием.

1. ВВЕДЕНИЕ 2. ЗАДАЧА 2. 1 Определение задачи 3. ОБЗОР АЛГОРИТМОВ 3. 1 Сопоставления строк 3. 2 Расстояния между строками 3. 2.1 Обобщенные задачи 3. 3 Нечеткое сопоставление строк 3. 3.1 Специальные устройства 3. 4 Максимальная повторяющаяся подстрока 4. АЛГОРИТМЫ 4. 1 Поиск образцов 4. 1.1 Наивный подход 4. 1.2 Кнут-Моррис-Пратт 4. 1.3 Бойер-Мур 4. 1.4 Бойер-Мур-Хорспул 4. 1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение 4. 1.6 Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена 4. 1.7 Харрисон 4. 1.8 Карп-Рабин 4. 2 Расстояние между строками и самая длинная общая подпоследовательность 4. 2.1 Вагнер-Фишер 4. 2.2 Хиршберг 4. 2.3 Хант-Шиманский 4. 2.4 Машек-Патерсон 4. 2.5 Укконен 4. 2.6 Самая тяжелая общая подпоследовательность 4. 3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК 4. 3.1 k несовпадений - Ландау-Вишкин 4. 3.2 k различий - Ландау-Вишкин 4. 4 Самая длинная повторяющася подстрока 4. 4.1 Наивный подход 4. 4.2 Суффиксные деревья 5. НАЗАД, К ИСХОДНОЙ ЗАДАЧЕ 5. 1 Система 5. 2 Задача 6. ПРИЛОЖЕНИЕ A: АСИМПТОТИЧЕСКАЯ ЗАПИСЬ 7. ЛИТЕРАТУРА

Дата последней модификации: 10 октября 2000 г.