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