Поиск самой длинной палиндроновой подпоследовательности с меньшим объемом памяти

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

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

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

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

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

Самая длинная подпоследовательность палиндрома (LPS) строки - это просто Самая длинная общая подпоследовательность сама и ее обратная. (Я построил это решение после решения другого связанного вопроса, который запрашивает "Longest Increasing Subsequence" последовательности). Поскольку это просто вариант 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 достигает этой границы, связывая кандидатные подпоследовательности, но с палиндромами это сложнее, потому что здесь важно не предыдущий элемент в подпоследовательности, а первый. Кто-нибудь знает, возможно ли это сделать, или оптимальная память предыдущих решений?

Ответ 1

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

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

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

Рассмотрим это для character.

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

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

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

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

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

Ответ 2

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

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

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