Проблема с самой длинной повторяющейся подстрокой - Википедия - Longest repeated substring problem

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

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

Эта проблема может быть решена в линейном времени и пространстве. ${ Displaystyle Theta (п)}$ путем создания суффиксное дерево для строки (с добавленным специальным символом конца строки, например '$') и поиск самого глубокого внутреннего узла в дереве. Глубина измеряется количеством символов, пройденных от корня. Строка, обозначенная ребрами от корня до такого узла, является самой длинной повторяющейся подстрокой. Проблема поиска самой длинной подстроки с хотя бы ${ displaystyle k}$ вхождения могут быть решены путем предварительной обработки дерева для подсчета числа конечных потомков для каждого внутреннего узла, а затем нахождения самого глубокого узла с как минимум ${ displaystyle k}$ листовые потомки, не имеющие детей. Чтобы избежать перекрывающихся повторов, вы можете проверить, что список длин суффиксов не содержит последовательных элементов с разницей в длине меньше, чем префикс.

На рисунке со строкой «ATCGATCGA $» самая длинная подстрока, которая повторяется как минимум дважды, - это «ATCGA».

внешняя ссылка

Этот алгоритмы или же структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.