Задача о наибольшей общей подпоследовательности-палиндроме — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
Строка 1: | Строка 1: | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где эта последовательность также должна быть палиндромом. | '''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где эта последовательность также должна быть палиндромом. | ||
{{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}} | {{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}} |
Текущая версия на 19:21, 4 сентября 2022
Задача о наибольшей общей подпоследовательности (англ. longest common subsequence (LCS)) - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где эта последовательность также должна быть палиндромом.
Определение: |
Палиндромом (англ. palindrom) называется строка, которая одинаково читается как слева направо, так и справа налево. |
Наибольшая общая подпалиндромная подпоследовательность (англ. The longest common palindromic sub-sequence (LCPS)) - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом.
Постановка задачи
Мы предполагаем конечный алфавит
. Для строки , мы обознамич его подстроку как . Для двух строк и , если общая подпоследовательность строк и является палиндромом, то называется общей подпалиндромной подпоследовательностью (англ. common palindromicsubsequence). Общая подпалиндромная последовательность, имеющая максимальную длину, называется наибольшей общей подпалиндромной подпоследовательностью (англ. The longest common palindromic sub-sequence (LCPS)) и мы обозначим её как .