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