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