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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение (алгоритм Манакера))
Строка 7: Строка 7:
  
 
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
 
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.  
== Решение (алгоритм Манакера) ==
+
== Решение ==
 +
=== Алгоритм Манакера ===
 
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
 
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
  
Строка 27: Строка 28:
  
 
Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичны.
 
Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов <tex>d_1[]</tex>; для массива чётных палиндромов <tex>d_2[]</tex> все рассуждения аналогичны.
 +
==== Оценка асимптотики ====
 +
==== Псевдокод ====
 +
 +
=== Тривиальный алгоритм ===
 +
 +
==== Псевдокод ====
  
 
== См. также ==
 
== См. также ==
Строка 35: Строка 42:
 
*[[wikipedia:Palindrome|Wikipedia — Palindrome]]
 
*[[wikipedia:Palindrome|Wikipedia — Palindrome]]
 
*[[wikipedia:ru:Палиндром|Википедия — Палиндром]]
 
*[[wikipedia:ru:Палиндром|Википедия — Палиндром]]
 +
*[http://e-maxx.ru/algo/palindromes_count Нахождение всех подпалиномов]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Версия 21:56, 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

Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. [math]j-d_1[j]+1 \le l[/math] (или, что то же самое, [math]i+d_1[j]-1 \ge r[/math]). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить [math]d_1[i]=d_1[j][/math] будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции [math]i[/math] палиндром имеет такую же длину.

На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить [math]d_1[i]=r-i[/math]. После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение [math]d_1[i][/math], пока это возможно.

Иллюстрация этого случая (на ней палиндром с центром в [math]j[/math] изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром): IMG2

В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения [math](l,r)[/math] после вычисления очередного значения [math]d_1[i][/math].

Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов [math]d_1[][/math]; для массива чётных палиндромов [math]d_2[][/math] все рассуждения аналогичны.

Оценка асимптотики

Псевдокод

Тривиальный алгоритм

Псевдокод

См. также

Литература