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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Псевдокод)
(1)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
 
Задача о '''наибольшей подпоследовательности-палиндрома''' — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
−
 
 
== Определения ==
 
== Определения ==
−
 
 
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
 
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
  
Строка 9: Строка 7:
  
 
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
 
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
−
== Решение ==
+
== Решение (алгоритм Манакера) ==
−
[[Файл:Palindrome11.png|200px|thumb|right|Массив длин подпоследовательностей-палиндромов]]
+
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
−
[[Файл:Palindrome12.png|200px|thumb|right|Наглядный массив переходов]]
 
−
Обозначим данную последовательность через <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>.
 
−
 
 
−
Начнем решать задачу с простых подпоследовательностей. Для последовательности из одного элемента (то есть подпоследовательности вида <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>.
 
−
 
 
−
== Пример ==
 
−
Рассмотрим решение на примере последовательности '''''ABACCBA'''''. Первым делом заполняем диагональ массива единицами, они будут соответствовать подпоследовательностями <tex>S(i, i)</tex> из одного элемента. Затем начинаем рассматривать подпоследовательности длины два. Во всех подпоследовательностях, кроме <tex>S(4, 5)</tex>, элементы различны, поэтому в соответствующие ячейки запишем <tex>1</tex>, а в <tex>L[4][5]</tex> — <tex>2</tex>.
 
−
 
 
−
Получается, что мы будем заполнять массив по диагоналям, начиная с главной диагонали, ведущей из левого верхнего угла в правый нижний. Для подпоследовательностей длины <tex>3</tex> получаются следующие значения: в подпоследовательности '''''ABA''''' первый и последний элемент равны, поэтому <tex>L[1][3] = L[2][2] + 2</tex>. В остальных подпоследовательностях первый и последний элементы различны.
 
−
 
 
−
'''''BAC''''': <tex>L[2][4] = max(L[2][3], L[3][4]) = 1</tex>
 
  
−
'''''ACC''''': <tex>L[3][5] = max(L[3][4], L[4][5]) = 2</tex>
+
Для быстрого вычисления будем поддерживать '''границы''' <tex>(l, r)</tex> самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением <tex>r</tex>). Изначально можно считать <tex>l=0, r=-1</tex>.
  
−
'''''CCB''''': <tex>L[4][6] = max(L[4][5], L[5][6]) = 2</tex>
+
Итак, пусть вычисляем значение <tex>d_1[i]</tex> для очередного <tex>i</tex>, при этом все предыдущие значения <tex>d_1[]</tex> уже подсчитаны.
  
−
'''''CBA''''': <tex>L[5][7] = max(L[5][6], L[6][7]) = 1</tex>
+
* Если <tex>i</tex> не находится в пределах текущего палиндрома, т.е. <tex>i>r</tex>, то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение <tex>d_1[i]</tex>, и проверять каждый раз — правда ли текущая подпоследовательность <tex>[i-d_1[i];i+d_1[i]]</tex> является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки <tex>S</tex> — останавливаемся: окончательно посчитали значение <tex>d_1[i]</tex>. После этого мы должны не забыть обновить значения <tex>(l,r)</tex>.
  
−
Продолжая далее аналогичные рассуждения, заполним все ячейки под диагональю и в ячейке <tex>L[1][7]</tex> получим ответ <tex>(6)</tex>.
+
* Рассмотрим случай, когда <tex>i \le r</tex>. Попробуем извлечь часть информации из уже подсчитанных значений <tex>d_1[]</tex>. А именно, отразим позицию <tex>i</tex> внутри палиндрома <tex>(l,r)</tex>, т.е. получим позицию <tex>j=l+(r-i)</tex>, и рассмотрим значение <tex>d_1[j]</tex>. Поскольку <tex>j</tex> — позиция, симметричная позиции <tex>i</tex>, то почти всегда можно просто присвоить <tex>d_1[i]=d_1[j]</tex>. Иллюстрация этого отражения (палиндром вокруг  фактически "копируется" в палиндром вокруг <tex>i</tex>):'''IMG1'''
  
−
Если же в задаче необходимо вывести не длину, а саму подпоследовательность-палиндром, то дополнительно к массиву длин мы должны построить массив переходов — для каждой ячейки запомнить, какой из случаев был реализован.
 
  
−
== Псевдокод ==
 
−
Размещаем граничные случаи: <tex>F(I, I) = 1</tex> и <tex>F(I, J) = 0</tex>, если <tex>I > J</tex>. Теперь в рассматриваемой подстроке отделяем первый символ. Есть две возможности (какая из них реализуется, пока не знаем). Отделенный символ не участвует в образовании максимального подпоследовательности-палиндрома — тогда <tex>F(I, J) = F(I + 1, J)</tex>. Если же участвует, то ищем в подстроке с конца символ, совпадающий с отделенным (пусть его позиция <tex>K</tex>), тогда <tex>F(I, J) = 2 + F(I + 1, K – 1)</tex>. Надо предусмотреть еще случай <tex>I = K</tex>, а затем отсекать рекурсию.
 
−
Получается следующая функция:
 
−
  Function F(i, j)
 
−
    if L[i, j] == -1
 
−
      k = j
 
−
      while S[i] <> S[k]
 
−
        k--
 
−
      R1 = F(i + 1, j)
 
−
      if i <> k
 
−
        R2 = F(i + 1, k - 1) + 2
 
−
      else
 
−
        R2 = 1
 
−
      if R1 > R2
 
−
        L[i, j] = R1
 
−
      else
 
−
        L[i, j] = R2
 
−
    return L[i, j]
 
  
 
== См. также ==
 
== См. также ==

Версия 21:41, 12 декабря 2012

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

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

Определения

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


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


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

Решение (алгоритм Манакера)

Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив [math]d_1[][/math]; решение для палиндромов чётной длины (т.е. нахождение массива [math]d_2[][/math]) получится небольшой модификацией этого.

Для быстрого вычисления будем поддерживать границы [math](l, r)[/math] самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением [math]r[/math]). Изначально можно считать [math]l=0, r=-1[/math].

Итак, пусть вычисляем значение [math]d_1[i][/math] для очередного [math]i[/math], при этом все предыдущие значения [math]d_1[][/math] уже подсчитаны.

  • Если [math]i[/math] не находится в пределах текущего палиндрома, т.е. [math]i\gt r[/math], то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение [math]d_1[i][/math], и проверять каждый раз — правда ли текущая подпоследовательность [math][i-d_1[i];i+d_1[i]][/math] является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки [math]S[/math] — останавливаемся: окончательно посчитали значение [math]d_1[i][/math]. После этого мы должны не забыть обновить значения [math](l,r)[/math].
  • Рассмотрим случай, когда [math]i \le r[/math]. Попробуем извлечь часть информации из уже подсчитанных значений [math]d_1[][/math]. А именно, отразим позицию [math]i[/math] внутри палиндрома [math](l,r)[/math], т.е. получим позицию [math]j=l+(r-i)[/math], и рассмотрим значение [math]d_1[j][/math]. Поскольку [math]j[/math] — позиция, симметричная позиции [math]i[/math], то почти всегда можно просто присвоить [math]d_1[i]=d_1[j][/math]. Иллюстрация этого отражения (палиндром вокруг фактически "копируется" в палиндром вокруг [math]i[/math]):IMG1


См. также

Литература

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