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

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

Определения

Определение:

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

Определение:

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

Например, 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

См. также

• Задача о наибольшей общей подпоследовательности
• Задача о наибольшей возрастающей подпоследовательности

Литература

• Wikipedia — Palindrome
• Википедия — Палиндром
• E-Maxx - Нахождение всех подпалиндромов