Вычисление длиннейшей общей подстроки
с помощью суффиксных массивов
Аннотация
Пусть даны $n$ строк общей длины $L$ и задано число $k_0$, $2 \le k_0
\le n$. Требуется найти наибольшую общую подстроку $k_0$ строк по всем
наборам. Для этой задачи известны алгоритмы, позволяющие получить
решение за время $O(L)$.
Эти решения используют понятие суффиксных деревьев, из-за чего размер
требуемой памяти (пропорциональный размеру алфавита) велик. Мы
предлагаем алгоритм, основанный на применении суффиксных массивов и
требующий $O(L)$ времени и $O(L)$ памяти.
Будут введены понятия наибольшего общего префикса, суффиксных массивов
и декартовых деревьев. Кроме того, будет описан способ построения
суффиксного массива за линейное от длины текста время.