Неформальная постановка задачи:
Для строки, например, , мы хотим, чтобы некоторые буквы были окрашены в красный цвет, а некоторые - в синий (а некоторые нет), чтобы чтение только красных букв слева направо давало тот же результат, что и чтение только синих букв.
В примере мы могли бы покрасить их так:
Поэтому мы говорим, что - это повторяющаяся подпоследовательность . Это также самая длинная повторяемая подпоследовательность (которую легко проверить).A C C A B B A B
Можем ли мы эффективно вычислить самые длинные повторные подпоследовательности?
Формальный вопрос:
Трудно ли NP решить для строки и некоторого , существует ли в строке повторяющаяся подпоследовательность длины ?к
- Если так: какую проблему можно свести к этой проблеме?
- Если нет: что такое эффективный алгоритм? (очевидно, этот алгоритм может быть использован для вычисления самой длинной повторяющейся подпоследовательности)
Бонусный вопрос:
Будут ли они всегда повторяться в подпоследовательности длины если размер алфавита ограничен константой?
(Известно, что это верно для двоичных алфавитов.)
Изменить 2: Отрицательный ответ на бонусный вопрос уже известен для алфавитов размером не менее . Фактически для алфавитов размером Σ существуют строки с самыми длинными повторяющимися подпоследовательностями длиной всего O (n · Σ ^ {- 1/2}) . Случайных строк достаточно, чтобы показать это. Результат уже существовал, но я его упустил.
Редактировать: Примечание:
Некоторые люди имеют в виду «подстрока», когда говорят «подпоследовательность». Я не. Это не проблема поиска подстрок дважды.
Ответы:
Это может быть решено вG (i,j) S S[i]=S[j] u v u v
полиномиальное времяпутем построения графа где каждый узел представляет точку в некоторой повторяющейся подпоследовательности такой что . Край между узлами и означает, что можно продолжить с помощью чтобы сформировать повторяющуюся подпоследовательность длины 2.( i , j ) S S [ i ] = S [ j ] u v u v1. Найдите узлы. Это можно сделать за , построив отсортированный список индексов для каждого символа , а затем перечислив уникальные пары. Здесь не более узлов.c m = n 2O(n2) c m=n2
2. Найдите края. Требуется время, чтобы проверить, может ли узел быть продолжен узлом , поэтому, учитывая все пары этот шаг занимает времени.u v ( u , v ) O ( м 2 )O(1) u v (u,v) O(m2)
3. Обратите внимание, что самый длинный путь в может не быть действительной повторяющейся подпоследовательностью. Рассмотрим пути и . Если существует ребро то является допустимой повторяющейся подпоследовательностью длины 3. Следовательно, требуется время, чтобы найти все повторяющиеся подпоследовательности длины 3. В общем случае требуется линейное время, чтобы проверить, являются ли два действительных пути длины можно объединить в правильный путь длины .a b b c a c a b c O ( m 4 ) n n + 1G ab bc ac abc O(m4) n n+1
4. Повторяйте шаг 3, пока пути не будут найдены.
источник