Изменения

Задача о '''[[Задача о наибольшей общей подпоследовательности-палиндрома]]''' (англ. ''longest common subsequence(LCS)'') — это задача поиска длины наибольшей общей подпоследовательности-палиндромаклассическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, которую можно получить вычеркиванием некоторых букв из данных последовательностейгде эта последовательность также должна быть палиндромом.== Определения =={{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}}{{Определение|definition='''ПодпоследовательностьюНаибольшая общая подпалиндромная подпоследовательность''' (англ. ''The longest common palindromic sub-палиндромом данной строкиsequence (LCPS)''' называется последовательность символов из данной строки) - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, не обязательно идущих подрядкоторая находит наибольшую общую подпоследовательность среди двух строк так, являющаяся что она также является палиндромом. }} ==Постановка задачи==Мы предполагаем конечный алфавит <tex>\sum</tex>. Для строки <tex>X</tex>, мы обознамич его подстроку <tex>x_{i}...x_{Определение|definition=Последовательность j} (1 \leqslant i \leqslant j \leqslant n)</tex> как <tex> Z X_{i,j}</tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей Для двух строк <tex> X </tex> и <tex> Y </tex>, если общая подпоследовательность <tex> Z </tex> является подпоследовательностью как строк <tex> X </tex>, так и <tex> Y </tex>.}}является палиндромом, то <tex>Z</tex> называется '''общей подпалиндромной подпоследовательностью''Например'(англ. ''common palindromicsubsequence''). Общая подпалиндромная последовательность, имеющая максимальную длину, называется '''наибольшей общей подпалиндромной подпоследовательностью''HELOLEH'(англ. '''' является подпоследовательностьюThe longest common palindromic sub-палиндромом строки '''''HTEOLFEOLEH'''sequence (LCPS)'') и мы обозначим её как <tex>LCPS(X,Y)</tex>. ==Динамическое программирование==