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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
м (rollbackEdits.php mass rollback)
 
(не показано 88 промежуточных версий 6 участников)
Строка 1: Строка 1:
Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
+
{{Определение|definition='''Палиндромом''' (англ. <i>Palindrome</i>) называется строка, которая одинаково читается как слева направо, так и справа налево.}}
 +
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' (англ. <i>Largest Palindromic Subsequence</i>) называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
 +
Например, '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
  
== Определения ==
+
{{Задача
 +
|definition =  
 +
Задача о '''наибольшей подпоследовательности-палиндроме''' {{---}} это задача о поиске наибольшей подпоследовательности, которую можно получить вычеркиванием некоторых букв из данной последовательности таким образом, что оставшаяся подпоследовательность будет палиндромом.
 +
}}
  
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
+
== Решение ==
 +
Обозначим данную последовательность через <tex>S</tex>, а ее элементы {{---}} через <tex>S[i], 0 \leqslant  i \leqslant  n - 1</tex>, где <tex>n</tex> {{---}} длина строки <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>.
  
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
+
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида <tex>S(i, i)</tex>) ответ очевиден {{---}} ничего вычеркивать не надо, такая строка будет искомой подпоследовательностью-палиндромом. Для последовательности из двух элементов <tex>S(i, i + 1)</tex> возможны два варианта: если элементы равны, то мы имеем подпоследовательность-палиндром, ничего вычеркивать не надо. Если же элементы не равны, то вычеркиваем любой.
  
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
+
Пусть теперь нам дана подпоследовательность <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>. Таким образом получаем следующее рекуррентное соотношение:  
== Решение ==
+
 
[[Файл:Palindrome11.jpg|200px|thumb|right|Массив длин подпоследовательностей-палиндромов]]
+
<tex>
[[Файл:Palindrome12.jpg|200px|thumb|right|Наглядный массив переходов]]
+
L[i][j] =
Обозначим данную последовательность через <tex>S</tex>, а ее элементы — через <tex>S[i], 1 \le i \le n</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>.
+
\begin{cases}
 +
1, & i = j\\
 +
0, & i > 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}
 +
</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>.
+
Каждый элемент массива мы вычисляем <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(4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[4][5]</tex> <tex>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>
  
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[1][3] = L[2][2] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.
+
'''''ACC''''': <tex>L[2][4] = \max(L[2][3], L[3][4]) = 2</tex>
  
'''''BAC''''': <tex>L[2][4] = max(L[2][3], L[3][4]) = 1</tex>
+
'''''CCB''''': <tex>L[3][5] = \max(L[3][4], L[4][5]) = 2</tex>
  
'''''ACC''''': <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>
  
'''''CCB''''': <tex>L[4][6] = max(L[4][5], L[5][6]) = 2</tex>
+
Продолжая далее аналогичные рассуждения, заполним все ячейки над диагональю и в ячейке <tex>L[0][6]</tex> получим ответ {{---}} <tex>6</tex>.
  
'''''CBA''''': <tex>L[5][7] = max(L[5][6], L[6][7]) = 1</tex>
+
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов {{---}} для каждой ячейки запомнить, какой из случаев был реализован.
  
Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке <tex>L[1][7]</tex> получим ответ <tex>(6)</tex>.
+
Последовательность заполнения массива и массив переходов см. на изображениях ниже.
  
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
+
[[Файл:Palindrome11.png|200px|Заполнение массива длин (1)]]
 +
[[Файл:Palindrome12.png|200px|Заполнение массива длин (2)]]
 +
[[Файл:Palindrome13.png|200px|Заполнение массива длин (3)]]
 +
[[Файл:Palindrome14.png|200px|Заполнение массива длин (4)]]
 +
[[Файл:Palindrome15.png|200px|Массив переходов]]
  
== Литература ==
+
== Псевдокод ==
[http://en.wikipedia.org/wiki/Palindrome Wikipedia — Palindrome]
+
Перед вызовом процедуры заполняем <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>.
  
[http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D0%BB%D0%B8%D0%BD%D0%B4%D1%80%D0%BE%D0%BC Википедия — Палиндром]
+
'''Функция для вычисления длины палиндрома''':
 +
*Границы исходной последовательности: <tex> \mathtt{left, right}</tex>
 +
<code style = "display: inline-block;">
 +
  '''int''' palSubSeq(left: '''int''', right: '''int'''):
 +
    '''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> \mathtt{left, right}</tex>
 +
*Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: <tex> \mathtt{palLeft, palRight}</tex>
 +
<code style = "display: inline-block;">
 +
  <font color=green>// palindrome {{---}} массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома</font>
 +
  palChars(left: '''int''', right: '''int''', palLeft: '''int''', palRight: '''int'''):
 +
    '''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>
  
 
== См. также ==
 
== См. также ==
[http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%BE%D0%B1%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Задача о наибольшей общей подпоследовательности]
+
* [[Задача о наибольшей общей подпоследовательности]]
 +
* [[Задача о наибольшей возрастающей подпоследовательности]]
 +
* [[Задача о наибольшей общей палиндромной подпоследовательности]]
  
[http://neerc.ifmo.ru/wiki/index.php?title=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B5%D0%B9_%D0%B2%D0%BE%D0%B7%D1%80%D0%B0%D1%81%D1%82%D0%B0%D1%8E%D1%89%D0%B5%D0%B9_%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8 Задача о наибольшей возрастающей подпоследовательности]
+
==Источники информации==
 +
* [[wikipedia:ru:Палиндром|Википедия {{---}} Палиндром]]
 +
* [[wikipedia:Palindrome|Wikipedia {{---}} Palindrome]]
 +
* [http://wcipeg.com/wiki/Longest_palindromic_subsequence Wikipedia {{---}} Longest palindromic subsequence]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Текущая версия на 19:42, 4 сентября 2022

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


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

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


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


Решение

Обозначим данную последовательность через [math]S[/math], а ее элементы — через [math]S[i], 0 \leqslant i \leqslant n - 1[/math], где [math]n[/math] — длина строки [math]S[/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].

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

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

Заполнение массива длин (1) Заполнение массива длин (2) Заполнение массива длин (3) Заполнение массива длин (4) Массив переходов

Псевдокод

Перед вызовом процедуры заполняем [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] \mathrm{palSubSeq(0, N - 1)}[/math]. Искомая же длина будет записана в ячейке [math]L[0][N-1][/math].

Функция для вычисления длины палиндрома:

  • Границы исходной последовательности: [math] \mathtt{left, right}[/math]

 int palSubSeq(left: int, right: int):
   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]

Процедура для построения искомого палиндрома:

  • Границы исходной последовательности: [math] \mathtt{left, right}[/math]
  • Границы искомой подпоследовательности-палиндрома, где правой границей будет длина найденного палиндрома: [math] \mathtt{palLeft, palRight}[/math]

 // palindrome — массив символов, где в palindrome[i] содержится символ искомой последовательности-палиндрома
 palChars(left: int, right: int, palLeft: int, palRight: int):
   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--

См. также

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