Задача о наибольшей подпоследовательности-палиндроме
Задача о наибольшей подпоследовательности-палиндрома — это задача поиска длины наибольшей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данной последовательности.
Определения
| Определение: |
| Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. |
| Определение: |
| Подпоследовательностью-палиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. |
Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.
Решение
Для решения этой задачи будет необходимо перебрать все подпоследовательности-палиндромы данной последовательности. Наиболее оптимально это можно сделать с помощью алгоритма Манакера.
Алгоритм Манакера
Сначала поймем как находить все подпоследовательности-палиндромы нечётной длины, т.е. вычислять массив ; решение для палиндромов чётной длины (т.е. нахождение массива ) получится небольшой модификацией этого.
Для быстрого вычисления будем поддерживать границы самого правого из обнаруженных палиндромов (т.е. палиндрома с наибольшим значением ). Изначально можно считать .
Итак, пусть вычисляем значение для очередного , при этом все предыдущие значения уже подсчитаны.
- Если не находится в пределах текущего палиндрома, т.е. , то просто выполним тривиальный алгоритм. Т.е. будем последовательно увеличивать значение , и проверять каждый раз — правда ли текущая подпоследовательность является палиндромом. Когда найдем первое расхождение, либо когда дойдем до границ строки — останавливаемся: окончательно посчитали значение . После этого мы должны не забыть обновить значения .
- Рассмотрим случай, когда . Попробуем извлечь часть информации из уже подсчитанных значений . А именно, отразим позицию внутри палиндрома , т.е. получим позицию , и рассмотрим значение . Поскольку — позиция, симметричная позиции , то почти всегда можно просто присвоить .
Однако здесь есть тонкость, которую надо обработать правильно: когда "внутренний палиндром" достигает границы внешнего или вылазит за неё, т.е. (или, что то же самое, ). Поскольку за границами внешнего палиндрома никакой симметрии не гарантируется, то просто присвоить будет уже некорректно: у нас недостаточно сведений, чтобы утверждать, что в позиции палиндром имеет такую же длину.
На самом деле, чтобы правильно обрабатывать такие ситуации, надо "обрезать" длину палиндрома, т.е. присвоить . После этого следует пустить тривиальный алгоритм, который будет пытаться увеличить значение , пока это возможно.
В завершение описания алгоритма сталось только напомнить, что надо не забывать обновлять значения после вычисления очередного значения .
Также повторимся, что выше описано рассуждение для вычисления массива нечётных палиндромов ; для массива чётных палиндромов все рассуждения аналогичны.
Оценка асимптотики
На первый взгляд не очевидно, что данный алгоритм имеет линейную асимптотику: при вычислении ответа для определённой позиции в нем нередко запускается тривиальный алгоритм поиска палиндромов.
Однако более внимательный анализ показывает, что алгоритм всё же линеен. (Стоит сослаться на алгоритм построения Z-функции строки, который внутренне сильно напоминает данный алгоритм, и работает также за линейное время.)
В самом деле, легко проследить по алгоритму, что каждая итерация, производимая тривиальным поиском, приводит к увеличению на один границы . При этом уменьшений по ходу алгоритма происходить не может. Следовательно, тривиальный алгоритм в сумме совершит лишь действий.
Учитывая, что, кроме тривиальных поисков, все остальные части алгоритма Манакера очевидно работают за линейное время, мы и получаем итоговую асимптотику: .
Псевдокод
Для случая подпоследовательностей нечётной длины, т.е. для вычисления массива , получаем такой код:
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
Для подпоследовательностей чётной длины, т.е. для вычисления массива , лишь немного меняются арифметические выражения:
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
Тривиальный алгоритм
Это алгоритм, который для поиска ответа в позиции раз за разом пробует увеличить ответ на единицу, каждый раз сравнивая пару соответствующих символов.
Такой алгоритм слишком медленен, весь ответ он может посчитать лишь за время
Псевдокод
Реализация тривиального алгоритма:
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]
