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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
== Решение ==
 
== Решение ==
 
Для решения этой задачи будет необходимо перебрать все подпоследовательности-палиндромы данной последовательности. Наиболее оптимально это можно сделать с помощью алгоритма Манакера.
 
Для решения этой задачи будет необходимо перебрать все подпоследовательности-палиндромы данной последовательности. Наиболее оптимально это можно сделать с помощью алгоритма Манакера.
 +
 +
=== Тривиальный алгоритм ===
 +
Это алгоритм, который для поиска ответа в позиции  раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов.
 +
 +
Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время <tex>O(n^2)</tex>
 +
==== Псевдокод ====
 +
Реализация тривиального алгоритма:
 +
 +
  List d1(n),  d2(n)
 +
  for i = 0 to n
 +
    d1[i] = 1
 +
    while i - d1[i] >= 0 && i + d1[i] < n && s[i-d1[i]] == s[i+d1[i]]
 +
      ++d1[i]
 +
    d2[i] = 0;
 +
    while i - d2[i] - 1 >= 0 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]
 +
      ++d2[i]
 +
 
=== Алгоритм Манакера ===
 
=== Алгоритм Манакера ===
 
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
 
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив <tex>d_1[]</tex>; решение для палиндромов чётной длины (т.е. нахождение массива <tex>d_2[]</tex>) получится небольшой модификацией этого.
Строка 65: Строка 82:
 
     if i + k - 1 > r
 
     if i + k - 1 > r
 
       l = i - k,  r = i + k - 1
 
       l = i - k,  r = i + k - 1
 
=== Тривиальный алгоритм ===
 
Это алгоритм, который для поиска ответа в позиции  раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов.
 
 
Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время <tex>O(n^2)</tex>
 
==== Псевдокод ====
 
Реализация тривиального алгоритма:
 
 
  List d1(n),  d2(n)
 
  for i = 0 to n
 
    d1[i] = 1
 
    while i - d1[i] >= 0 && i + d1[i] < n && s[i-d1[i]] == s[i+d1[i]]
 
      ++d1[i]
 
    d2[i] = 0;
 
    while i - d2[i] - 1 >= 0 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]
 
      ++d2[i]
 
  
 
== См. также ==
 
== См. также ==

Версия 20:24, 13 декабря 2012

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

Определения

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


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


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

Решение

Для решения этой задачи будет необходимо перебрать все подпоследовательности-палиндромы данной последовательности. Наиболее оптимально это можно сделать с помощью алгоритма Манакера.

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

Это алгоритм, который для поиска ответа в позиции раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов.

Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время [math]O(n^2)[/math]

Псевдокод

Реализация тривиального алгоритма:

 List d1(n),  d2(n)
 for i = 0 to n
   d1[i] = 1
   while i - d1[i] >= 0 && i + d1[i] < n && s[i-d1[i]] == s[i+d1[i]]
     ++d1[i]
   d2[i] = 0;
   while i - d2[i] - 1 >= 0 && i + d2[i] < n && s[i - d2[i] - 1] == s[i + d2[i]]
     ++d2[i]

Алгоритм Манакера

Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив [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]

Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. [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] изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром

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

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

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

На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромов.

Однако более внимательный анализ показывает, что алгоритм всё же линеен. (Стоит сослаться на алгоритм построения Z-функции строки, который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.)

В самом деле, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы [math]r[/math]. При этом уменьшений [math]r[/math] по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм в сумме совершит лишь [math]O(n)[/math] действий.

Учитывая, что, кроме тривиальных поисков, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: [math]O(n)[/math].

Псевдокод

Для случая подпоследовательностей нечётной длины, т.е. для вычисления массива [math]d_1[][/math], получаем такой код:

 List d1(n)
 l = 0, r = -1
 for i = 0 to n
   k = (i > r ? 0 : min(d1[l + r - i], r - i)) + 1
   while i + k < n && i - k >= 0 && s[i+k] == s[i-k]
     ++k
   d1[i] = k--
   if i + k > r
     l = i - k,  r = i + k

Для подпоследовательностей чётной длины, т.е. для вычисления массива [math]d_2[][/math], лишь немного меняются арифметические выражения:

 List d2(n)
 l = 0, r = -1
 for i = 0 to n
   k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1
   while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k])
     ++k
   d2[i] = --k
   if i + k - 1 > r
     l = i - k,  r = i + k - 1

См. также

Литература