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

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

Определения

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

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

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

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

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

Последовательность [math] Z [/math] является общей подпоследовательностью (англ. common subsequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] Z [/math] является подпоследовательностью как [math] X [/math], так и [math] Y [/math].

Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.