Задача о наибольшей общей подпоследовательности-палиндроме — различия между версиями
Oxygen3 (обсуждение | вклад) |
|||
| Строка 1: | Строка 1: | ||
| − | '''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема. | + | '''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где это последовательность должна быть палиндромом. |
{{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}} | {{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}} | ||
'''Наибольшая общая подпоследовательность-палиндром''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом. | '''Наибольшая общая подпоследовательность-палиндром''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом. | ||
Версия 22:18, 11 декабря 2014
Задача о наибольшей общей подпоследовательности (англ. longest common subsequence (LCS)) - классическая и хорошо изученная проблема. В данной статье мы рассмотрим её модификацию, где это последовательность должна быть палиндромом.
| Определение: |
| Палиндромом (англ. palindrom) называется строка, которая одинаково читается как слева направо, так и справа налево. |
Наибольшая общая подпоследовательность-палиндром (англ. The longest common palindromic sub-sequence (LCPS)) - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом.
