68
правок
Изменения
Нет описания правки
{{Задача|definition == Определения ==Задача о '''наибольшей подпоследовательности-палиндроме''' {{---}} это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной последовательности таким образом, что оставшаяся подпоследовательность будет палиндромом.}}
== Решение ==Обозначим данную последовательность через <tex>S</tex>, а ее элементы {{---}} через <tex>S[i], 0 \leqslant i \leqslant n - 1</tex>, где <tex>n</tex> {{Определение|definition='''Палиндромом''' называется строка---}} длина строки <tex>S</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>) ответ очевиден {{Определение|definition='''Подпоследовательностью---}} ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом данной строки''' называется последовательность символов . Для последовательности из данной строкидвух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не обязательно идущих подряднадо. Если же элементы не равны, являющаяся палиндромомто вычеркиваем любой. }}
=== Асимптотика ===
Каждый элемент массива мы вычисляем <tex>1 </tex> раз за <tex>O(1)</tex> обращаясь к уже вычисленным элементам. Так как размер массива <tex>n \times n</tex>, то алгоритм работает за <tex>O(n^2)</tex>
== Пример ==
Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями <tex>S(i, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>S(3, 4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[3][4]</tex> {{---}} <tex>2</tex>. Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[50][2] = L[1][1] + 2</tex> — . В остальных подпоследовательностях первый и последний элементы различны. '''''BAC''''': <tex>L[1][3] = \max(L[1][2], L[2][3]) = 1</tex>.
'''''BACCCB''''': <tex>L[23][45] = \max(L[23][34], L[34][45]) = 12</tex>
'''''ACCCBA''''': <tex>L[34][56] = \max(L[34][45], L[45][56]) = 21</tex>
== Псевдокод ==
Перед вызовом процедуры заполняем <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> \mathrm{palSubSeq(0, N - 1)}</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex> или . '''Функция для вычисления длины палиндрома''':*Границы исходной последовательности: <tex>L[N-1][0]\mathtt{left, right}</tex> в зависимости от реализации.<codestyle = "display: inline-block;"> functiont pal'''int''' palSubSeq(ileft: '''int''', jright: '''int''') //i и j - границы строки S: '''if ''' L[ileft][jright] == -1 //L - массив длин k '''if''' s[left] = j= s[right] while S L[ileft] <> S[kright] k-- R1 = palpalSubSeq(i left + 1, jright - 1)+ 2 if i != k'''else''' R2 L[left][right] = palmax(palSubSeq(i left + 1, k right), palSubSeq(left, right - 1) + 2) '''return''' L[left][right]</code>'''Процедура для построения искомого палиндрома''':*Границы исходной последовательности: <tex> \mathtt{left, right}</tex>*Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: <tex> \mathtt{palLeft, palRight}</tex> else<code style = "display: inline-block;"> R2 <font color= 1green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font> palChars(left: '''int''', right: '''int''', palLeft: '''int''', palRight: '''int'''): '''while''' left <tex>\leqslant </tex> right '''if R1 > R2''' left == right '''and''' L[left][right] == 1 Lpalindrome[ipalLeft++]= S[jleft++] = R1 '''else''' L'''if''' S[left] == S[iright] palindrome[jpalLeft++] := R2S[left++] return palindrome[palRight--] = S[right--] '''else''' '''if''' L[left + 1][right] <tex> > </tex> L[ileft][jright - 1] left++ '''else''' right--
</code>
== См. также ==
* [[Задача о наибольшей общей подпоследовательности]]
* [[Задача о наибольшей возрастающей подпоследовательности]]
* [[Задача о наибольшей общей палиндромной подпоследовательности]]
==Источники информации==
* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]
* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]
* [http://wcipeg.com/wiki/Longest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]