Задача о наибольшей подпоследовательности-палиндроме

Задача:

Задача о наибольшей подпоследовательности — палиндроме (Largest Palindromic Subsequence) — это задача поиска длины наибольшей подпоследовательности — палиндроме которую можно получить вычеркиванием некоторых букв из данной последовательности.

Определения

Определение:

Палиндромом (Palindrome) называется строка, которая одинаково читается как слева направо, так и справа налево.

Определение:

Подпоследовательностью — палиндромом данной строки (Largest Palindromic Subsequence) называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом.

Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.

Решение

Обозначим данную последовательность через [math]S[/math], а ее элементы — через [math]S[i], 0 \leqslant i \leqslant n - 1[/math]. Будем рассматривать возможные подпоследовательности данной последовательности с [math]i - [/math]го по [math]j - [/math]ый символ включительно, обозначив её как [math]S(i, j)[/math]. Длины максимальных подпалиндромов для данной последовательности будем записывать в квадратный массив [math]L[/math]: [math]L[i][j][/math] — длина максимальной подпоследовательности — палиндрома, который можно получить из последовательности [math]S(i, j)[/math].

Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида [math]S(i, i)[/math]) ответ очевиден — ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов [math]S(i, i + 1)[/math] возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.

Пусть теперь нам дана подпоследовательность [math]S(i, j)[/math]. Если [math]S[i][/math] и [math]S[j][/math] элементы подпоследовательности не совпадают, то один из них нужно вычеркнуть. Тогда у нас останется подпоследовательность [math]S(i, j - 1)[/math] или [math]S(i + 1, j)[/math] — то есть мы сведем задачу к подзадаче: [math]L[i][j] = \max(L[i][j - 1], L[i + 1][j])[/math]. Если же первый и последний элементы равны, то мы можем оставить оба, но необходимо знать решение задачи [math]S(i + 1, j - 1):L[i][j] = L[i + 1][j - 1] + 2[/math]. Таким образом получаем следующее рекуррентное соотношение:

[math] L[i][j] = \begin{cases} 1, & i = j\\ 0, & i \gt j\\ L[i + 1][j - 1] + 2, & s[i] = s[j] \\ \max(L[i][j - 1], L[i + 1][j]), & s[i] \neq s[j] \end{cases} [/math]

Асимптотика

Каждый элемент массива мы вычисляем [math]1[/math] раз за [math]O(1)[/math] обращаясь к уже вычисленным элементам. Так как размер массива [math]n \times n[/math], то алгоритм работает за [math]O(n^2)[/math]

Пример

Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями [math]S(i, i)[/math] из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме [math]S(3, 4)[/math], элементы различны, поэтому в соответствующие ячейки запишем [math]1[/math], а в [math]L[3][4][/math] — [math]2[/math].

Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины [math]3[/math] получаются следующие значения: в подпоследовательности ABA первый и последний элемент равны, поэтому [math]L[0][2] = L[1][1] + 2[/math]. В остальных подпоследовательностях первый и последний элементы различны.

BAC: [math]L[1][3] = \max(L[1][2], L[2][3]) = 1[/math]

ACC: [math]L[2][4] = \max(L[2][3], L[3][4]) = 2[/math]

CCB: [math]L[3][5] = \max(L[3][4], L[4][5]) = 2[/math]

CBA: [math]L[4][6] = \max(L[4][5], L[5][6]) = 1[/math]

Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке [math]L[0][6][/math] получим ответ — [math]6[/math].

Если же в задаче необходимо вывести не длину, а саму подпоследовательность — палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.

Последовательность заполнения массива и массив переходов см. на изображениях ниже.

Псевдокод

Перед вызовом процедуры заполняем [math]L[][][/math] начальными значениями: [math]L[i][j] = 1[/math] если [math]i=j[/math], [math]L[i][j] = 0[/math], если [math]i\gt j[/math], в остальных случаях [math]L[i][j]=-1[/math]. При первом вызове функции в качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной [math] N [/math] вызов функции будет иметь следующий вид: [math]palSubSeq(0,N - 1)[/math]. Искомая же длина будет записана в ячейке [math]L[0][N-1][/math].

Функция для вычисления длины палиндрома ([math]left, right[/math] - границы исходной последовательности):

 palSubSeq(left, right):
   if L[left][right] == -1 
     if s[left] == s[right] 
       L[left][right] = palSubSeq(left + 1, right - 1) + 2
     else 
       L[left][right] = [math]max[/math](palSubSeq(left + 1, right), palSubSeq(left, right - 1))  
   return L[left][right]

Функция для построения искомого палиндрома ([math]left, right[/math] — границы исходной последовательности, [math]palLeft=0, palRight=L[0][n-1]-1[/math] — границы искомой):

 // palindrome — массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома
 palChars(left, right, palLeft, palRight)
   while left [math]\leqslant [/math] right
     if left == right and L[left][right] == 1
       palindrome[palLeft++] = S[left++]
     else
       if S[left] == S[right]
         palindrome[palLeft++] = S[left++]
         palindrome[palRight--] = S[right--]
       else
         if L[left + 1][right] [math] \gt  [/math] L[left][right - 1]
           left++
         else
           right--

Источники информации

• Wikipedia — Palindrome
• Википедия — Палиндром

См. также

• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности