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