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