Нахождение самой длинной палиндромной подпоследовательности с меньшим объемом памяти

Question

Я пытаюсь решить проблему динамического программирования из Введение в алгоритмы Кормема, 3-е издание (стр. 405), которое спрашивает следующее:

Палиндром - непустая строка какой-то алфавит, который читает то же самое вперед и назад. Примеры палиндромы все строки длины 1, civic, racecar и aibohphobia (боязнь палиндромов).

Дайте эффективный алгоритм поиска самый длинный палиндром, который является подпоследовательность заданной входной строки. Например, учитывая вход character, ваш алгоритм должен возврат carac.

Ну, я мог бы решить это двумя способами:

Первое решение:

Самая длинная подпоследовательность палиндрома (LPS) строки - это просто Самая длинная общая подпоследовательность самой себя и ее обратной последовательности. (Я построил это решение после решения другого связанного вопроса, который запрашивает Самая длинная возрастающая подпоследовательность последовательности). Поскольку это просто вариант LCS, он также требует времени O (n²) и памяти O (n²).

Второе решение:

Второе решение немного сложнее, но также следует общему шаблону LCS. Это происходит из-за повторения:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

Псевдокод для расчета длины lps следующий:

compute-lps(s, n):

    // palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    // palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    // palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

По-прежнему требуется O (n²) времени и памяти, если я хочу эффективно построить lps (потому что мне понадобятся все ячейки в таблице). Анализируя связанные проблемы, такие как LIS, которые могут быть решены с помощью подходов, отличных от LCS-подобных, с меньшим объемом памяти (LIS разрешима с O (n) -памятью), мне было интересно, возможно ли решить ее с помощью O (n) -памяти тоже.

LIS достигает этой границы, связывая возможные последовательности, но с палиндромами это сложнее, потому что здесь важен не предыдущий элемент в подпоследовательности, а первый. Кто-нибудь знает, возможно ли это сделать, или память предыдущих решений оптимальна?

Answer 1

Вот очень эффективная версия памяти.Но я не продемонстрировал, что это всегда O(n) памяти.(С шагом предварительной обработки он может лучше, чем O(n<sup>2</sup>) CPU, хотя O(n<sup>2</sup>) - наихудший случай.)

Начать с крайней левой позиции.Для каждой позиции следите за таблицей самых дальних точек, в которых вы можете сгенерировать отраженные подпоследовательности длиной 1, 2, 3 и т. Д. (Это означает, что подпоследовательность слева от нашей точки отражается справа.) ДляВ каждой отраженной подпоследовательности мы сохраняем указатель на следующую часть подпоследовательности.

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

Давайте рассмотрим это для character.

1. Начнем с того, что наш лучший палиндром -буква 'c' и наша зеркальная подпоследовательность достигаются парой (0, 11), которая находится на концах строки.
2. Далее рассмотрим 'c' в позиции 1. Наши лучшие зеркальные подпоследовательности в форме(length, end, start) сейчас [(0, 11, 0), (1, 6, 1)].(Я опущу связанный список, который вам нужно сгенерировать для фактического поиска палиндрома.
3. Далее рассмотрим h в позиции 2. Мы не улучшаем границы [(0, 11, 0), (1, 6, 1)].
4. Далее рассмотрим a в позиции 3. Мы улучшаем границы до [(0, 11, 0), (1, 6, 1), (2, 5, 3)].
5. Далее рассмотрим r в позиции 4. Мы улучшаем границы до [(0, 11, 0), (1, 10, 4), (2, 5, 3)]. (Это гдесвязанный список будет полезен.

Работая с остальной частью списка, мы не улучшаем этот набор границ.

Таким образом, мы получаем самый длинный зеркальный список длиной 2И мы следуем за связанным списком (который я не записал в этом описании, чтобы найти его ac. Поскольку концы этого списка находятся в позициях (5, 3), мы можем перевернуть список, вставить символ 4затем добавьте список, чтобы получить carac.

В общем случае максимальная память, которая потребуется, - это хранить все длины максимальных зеркальных подпоследовательностей, а также память для хранения связанных списков указанных подпоследовательностей.Как правило этобудет очень маленький объем памяти.

При классическом компромиссе память / ЦП вы можете предварительно обработать список один раз за время O(n), чтобы сгенерировать хэш-массив размером O(n), в котором появляются определенные элементы последовательности.Это может позволить вам сканировать «улучшение зеркальной подпоследовательности с этим соединением» без необходимости рассматривать всю строку, что, как правило, должно быть основной экономией ЦП для более длинных строк.

Answer 2

Первое решение в вопросе @Luiz Rodrigo неверно: самая длинная общая подпоследовательность (LCS) строки и ее обратное не обязательно являются палиндромом.

Пример: для строки CBACB CAB - это LCS строки инаоборот, и это явно не палиндром.Однако есть способ заставить его работать.После того, как LCS строки и ее обратного построены, возьмите левую половину (включая серединный символ для строк нечетной длины) и дополните ее правой частью обращенной левой половиной (не включая средний символ, если длина строки нечетная)).Очевидно, что это будет палиндром, и можно легко доказать, что это будет подпоследовательность строки.

Для вышеупомянутых LCS палиндром, построенный таким образом, будет CAC.