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

2014-12-09T11:26:17Z

217.66.159.22: /* Псевдокод */

Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.

== Определения ==
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Решение ==
Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 0 \le i \le n - 1</tex>. Будем рассматривать возможные подпоследовательности данной последовательности с <tex>i - </tex>го по <tex>j-</tex>ый символ включительно, обозначив её как <tex>S(i, j)</tex>. Длины максимальных подпалиндромов для данной последовательности будем записывать в квадратный массив <tex>L</tex>: <tex>L[i][j]</tex> — длина максимальной подпоследовательности-палиндрома, который можно получить из последовательности <tex>S(i, j)</tex>.

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

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

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

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

'''''BAC''''': <tex>L[1][3] = max(L[1][2], L[2][3]) = 1</tex>

'''''ACC''''': <tex>L[2][4] = max(L[2][3], L[3][4]) = 2</tex>

'''''CCB''''': <tex>L[3][5] = max(L[3][4], L[4][5]) = 2</tex>

'''''CBA''''': <tex>L[4][6] = max(L[4][5], L[5][6]) = 1</tex>

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

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

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

[[Файл:Palindrome11.png|200px|Заполнение массива длин (1)]]
[[Файл:Palindrome12.png|200px|Заполнение массива длин (2)]]
[[Файл:Palindrome13.png|200px|Заполнение массива длин (3)]]
[[Файл:Palindrome14.png|200px|Заполнение массива длин (4)]]
[[Файл:Palindrome15.png|200px|Массив переходов]]

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

'''Функция для вычисления длины палиндрома''' (<tex>left, right</tex> - границы исходной последовательности):
<code style = "display: inline-block;">
'''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] = max(palSubSeq(left + 1, right), palSubSeq(left, right - 1))
'''return''' L[left][right]
</code>
'''Функция для построения искомого палиндрома''' (<tex>left, right</tex> {{---}} границы исходной последовательности, <tex>palLeft=0, palRight=L[0][n-1]-1</tex> {{---}} границы искомой):
<code style = "display: inline-block;">
// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома
'''palChars'''(left, right, palLeft, palRight)
'''while''' left <tex>\leqslant</tex> 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] <tex> > </tex> L[left][right - 1]
left++
'''else'''
right--
</code>

== Литература ==
* [[wikipedia:Palindrome|Wikipedia — Palindrome]]
* [[wikipedia:ru:Палиндром|Википедия — Палиндром]]

== См. также ==
* [[Задача о наибольшей общей подпоследовательности]]
* [[Задача о наибольшей возрастающей подпоследовательности]]

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

Викиконспекты - Вклад участника [ru]

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