Алгоритмы на строках

Основные определения. Простые комбинаторные свойства слов

• Основные определения, связанные со строками
• Период и бордер, их связь
• Слово Фибоначчи
• Слово Туэ-Морса
• Декомпозиция Линдона[math]^\star[/math]
• Алгоритм Ландау-Шмидта[math]^\star[/math]
• Алгоритм Крочемора[math]^\star[/math]
• Алгоритм Мейна-Лоренца[math]^\star[/math]
• Алгоритм Манакера[math]^\star[/math]
• Дерево палиндромов[math]^\star[/math]

Поиск подстроки в строке

Точный поиск

• Наивный алгоритм поиска подстроки в строке
• Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа
• Поиск наибольшей общей подстроки двух строк с использованием хеширования
• Префикс-функция
• Алгоритм Кнута-Морриса-Пратта
• Автомат Кнута-Морриса-Пратта
• Z-функция
• Бор
• Алгоритм Ахо-Корасик
• Суффиксный автомат
• Алгоритм Бойера-Мура
• Алгоритм Апостолико-Крочемора[math]^\star[/math]
• Алгоритм Колусси[math]^\star[/math]
• Алгоритм Райта[math]^\star[/math]
• Алгоритм Shift-And[math]^\star[/math]
• Двусторонний алгоритм[math]^\star[/math]
• Турбо-алгоритм Бойера-Мура[math]^\star[/math]

Нечёткий поиск

• Алгоритм Ландау-Вишкина (k несовпадений)[math]^\star[/math]
• Алгоритм Ландау-Вишкина (k различий)[math]^\star[/math]

Суффиксное дерево

• Суффиксный бор
• Сжатое суффиксное дерево
• Алгоритм Укконена
• Алгоритм МакКрейта[math]^\star[/math]
• Алгоритм Фараха[math]^\star[/math]

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

• Суффиксный массив
• Построение суффиксного массива с помощью стандартных методов сортировки
• Алгоритм цифровой сортировки суффиксов циклической строки
• Алгоритм Касаи и др.
• Алгоритм Карккайнена-Сандерса
• Алгоритм поиска подстроки в строке с помощью суффиксного массива
• Количество подпалиндромов в строке[math]^\star[/math]