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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
(Псевдокод)
Строка 42: Строка 42:
 
При первой вызове функции, к качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 вызов функции булдет иметь следующий вид: <tex>pal(0,6)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>, где <tex>N</tex> — длина исходной строки.
 
При первой вызове функции, к качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 вызов функции булдет иметь следующий вид: <tex>pal(0,6)</tex>. Искомая же длина будет записана в ячейке <tex>L[0][N-1]</tex>, где <tex>N</tex> — длина исходной строки.
 
<code style = "display: inline-block;">
 
<code style = "display: inline-block;">
   '''pal'''(i, j) //i и j - границы строки S
+
   '''palSubSeq'''(left, right)
     '''if''' L[i][j] = -1 //L - массив длин
+
     '''if''' L[left][right] = -1  
      k = j
+
        '''if''' s[left] = s[right]  
      '''while''' S[i] <tex>\neq</tex> S[k]
+
            L[left][right] = palSubSeq(left + 1, right - 1) + 2
        k--
+
        '''else'''  
      R1 = pal(i + 1, j)
+
            L[left][right] = MAX(palSubSeq(left + 1, right), palSubSeq(left, right - 1))
      '''if''' i <tex>\neq</tex> k
+
     '''return''' L[left][right]
        R2 = pal(i + 1, k - 1) + 2
 
      '''else'''
 
        R2 = 1
 
      '''if''' R1 > R2
 
        L[i][j] = R1
 
      '''else'''
 
        L[i][j] = R2
 
     '''return''' L[i][j]
 
 
</code>
 
</code>
  

Версия 14:39, 19 декабря 2012

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


Определения

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


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

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

Решение

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

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

Асимптотика

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

Пример

Рассмотрим решение на примере последовательности ABACCBA. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями [math]S(i, i)[/math] из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме [math]S(4, 5)[/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]. При первой вызове функции, к качестве аргументов передаем индексы первого и последнего элементов исходной строки. Например для строки длиной 7 вызов функции булдет иметь следующий вид: [math]pal(0,6)[/math]. Искомая же длина будет записана в ячейке [math]L[0][N-1][/math], где [math]N[/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] = MAX(palSubSeq(left + 1, right), palSubSeq(left, right - 1))
   return L[left][right]

Литература

См. также