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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Алгоритм Манакера)
Строка 17: Строка 17:
 
* Если <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>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>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>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>.
 +
 
 +
[[Файл:Palindrome1.png|300px|thumb|right|палиндром вокруг  фактически "копируется" в палиндром вокруг <tex>i</tex>]]
  
 
Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. <tex>j-d_1[j]+1 \le l</tex> (или, что то же самое, <tex>i+d_1[j]-1 \ge r</tex>). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить <tex>d_1[i]=d_1[j]</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции <tex>i</tex> палиндром имеет такую же длину.
 
Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. <tex>j-d_1[j]+1 \le l</tex> (или, что то же самое, <tex>i+d_1[j]-1 \ge r</tex>). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить <tex>d_1[i]=d_1[j]</tex> будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции <tex>i</tex> палиндром имеет такую же длину.
Строка 23: Строка 25:
 
На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить <tex>d_1[i]=r-i</tex>. После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение <tex>d_1[i]</tex>, пока это возможно.
 
На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить <tex>d_1[i]=r-i</tex>. После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение <tex>d_1[i]</tex>, пока это возможно.
  
Иллюстрация этого случая (на ней палиндром с центром в <tex>j</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром): '''IMG2'''
+
:
 +
 
 +
[[Файл:Palindrome2.png|300px|thumb|right|палиндром с центром в <tex>j</tex> изображен уже "обрезанным" до такой длины, что он впритык помещается во внешний палиндром]]
  
 
В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения <tex>(l,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>.
 
В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения <tex>(l,r)</tex> после вычисления очередного значения <tex>d_1[i]</tex>.

Версия 19:39, 13 декабря 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]

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

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

Псевдокод

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

Псевдокод

См. также

Литература