Строки, бор, суффиксный массив (24 марта 2016)

1. Задачи на Ахо-Корасика
1. Найти минимальную по длине строку, которую можно прочитать двумя разными способами
2. T9. За ход можно выписать префикс любой из данных строк. Нужно за минимальное число ходов выписать весь текст.
3. T9+. За ход можно выписать подстроку любой из данных строк. Нужно за минимальное число ходов выписать весь текст.
4. Поиск самой длинной подстроки словароного слова, входящей в текст.
2. Преобразование суффиксных структур
1. Алгоритм построения сжатого суфф.дерева по суфф.массиву+LCP за O(n).
2. Суфф дерево → суфф массив + LCP
3. Задачи на суфф.структуры (суфф.массив, суфф.дерево)
1. Поиск слова в тексте
2. Количество подстрок
3. refrain: длина * количество вхождения → max
4. Общая подстрока двух строк. Обобщение: общая подстрока k строк.
5. [не успеем] LCP = Наибольший общий префикс = LCA в суффиксном дереве.
6. [не успеем] Подпалиндром. Максимальный по длине. Количество.
7. [не успеем] Общий подпалиндром.
8. [не успеем] Два самых длинных неперекрывающихся вхождения.
9. [не успеем] k-я подстрока строки