Проблема с самой длинной повторяющейся подстрокой
В информатике проблема самой длинной повторяющейся подстроки — это проблема поиска самой длинной подстроки строки , которая встречается как минимум дважды.
Эту задачу можно решить в линейном времени и пространстве. путем построения суффиксного дерева для строки (со специальным символом конца строки, например '$'), и поиска самого глубокого внутреннего узла в дереве с более чем одним дочерним элементом. Глубина измеряется количеством символов, пройденных от корня. Строка, образованная ребрами от корня до такого узла, является самой длинной повторяющейся подстрокой. Задача найти самую длинную подстроку, содержащую не менее Вхождения можно решить, сначала предварительно обработав дерево для подсчета количества листовых потомков для каждого внутреннего узла, а затем найдя самый глубокий узел с по крайней мере потомки листьев. Чтобы избежать перекрытия повторов, вы можете проверить, что в списке длин суффиксов нет последовательных элементов с разницей в длине префикса меньше.
На рисунке со строкой «ATCGATCGA$» самая длинная подстрока, которая повторяется не менее двух раз, — это «ATCGA».
Внешние ссылки
[ редактировать ]- Эллисон, Л. «Суффиксные деревья» . Проверено 14 октября 2008 г.
- Реализация на C самой длинной повторяющейся подстроки с использованием суффиксного дерева
- Онлайн-демо: самая длинная повторяющаяся подстрока
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |