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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Псевдокод)
(→‎Псевдокод)
Строка 39: Строка 39:
 
Приведем псевдокод заполнения массива длин подпоследовательностей-палендромов:
 
Приведем псевдокод заполнения массива длин подпоследовательностей-палендромов:
 
<code>
 
<code>
−
procedure FillPalMatrix(s: string);
+
  procedure FillPalMatrix(s) //s-исходная подпоследовательность
−
  for j:= 1 to n do begin
+
    for j = 1 to n
−
    Mat[j, j]:= 1;
+
      L[j, j] = 1 //L-массив длин
−
    for i:= j - 1 downto 1 do begin
+
      for i = j - 1 downto 1
−
      count:= Mat[i + 1, j];
+
        count = L[i + 1, j]
−
      t:=j;
+
        t = j
−
      while s[t] <> s[i] do dec(t);
+
        while s[t] <> s[i]  
−
      found:= t - i + 1;
+
          t--
−
      if t >= i + 2 then found:= Mat[i + 1, t - 1] + 2;
+
        found = t - i + 1
−
      if count < found then count:= found;
+
        if t >= i + 2
−
      Mat[i, j]:= count;
+
          found = L[i + 1, t - 1] + 2
 +
        if count < found
 +
          count = found
 +
        L[i, j] = count
 
</code>
 
</code>
  

Версия 21:47, 14 декабря 2012

Эта статья находится в разработке!

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

Определения

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


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


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

Решение

Массив длин подпоследовательностей-палиндромов
Наглядный массив переходов

Обозначим данную последовательность через [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].

Пример

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

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

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

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

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

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

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

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

Псевдокод

Приведем псевдокод заполнения массива длин подпоследовательностей-палендромов: 

 procedure FillPalMatrix(s) //s-исходная подпоследовательность
   for j = 1 to n
     L[j, j] = 1 //L-массив длин
     for i = j - 1 downto 1
       count = L[i + 1, j]
       t = j
       while s[t] <> s[i] 
         t--
       found = t - i + 1
       if t >= i + 2
         found = L[i + 1, t - 1] + 2
       if count < found
         count = found
       L[i, j] = count

Литература

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_подпоследовательности-палиндроме&oldid=27608»