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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Задача о '''наибольшей общей подпоследовательности-палиндрома''' (англ. ''longest common subsequence'') ...»)
 
Строка 1: Строка 1:
−
Задача о '''наибольшей общей подпоследовательности-палиндрома''' (англ. ''longest common subsequence'') — это задача поиска длины наибольшей общей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данных последовательностей.
+
'''[[Задача о наибольшей общей подпоследовательности]]''' (англ. ''longest common subsequence (LCS)'') - классическая и хорошо изученная проблема.
−
== Определения ==
+
{{Определение|definition='''Палиндромом''' (англ. ''palindrom'') называется строка, которая одинаково читается как слева направо, так и справа налево.}}
−
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
+
'''Наибольшая общая подпоследовательность-палиндром''' (англ. ''The longest common palindromic sub-sequence (LCPS)'') - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом.
−
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
 
−
{{Определение|definition=Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
 
−
}}
 
−
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
 

Версия 17:01, 29 ноября 2014

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

Определение:
Палиндромом (англ. palindrom) называется строка, которая одинаково читается как слева направо, так и справа налево.

Наибольшая общая подпоследовательность-палиндром (англ. The longest common palindromic sub-sequence (LCPS)) - задача, являющаяся интересным вариантом классической задачи о поиске наибольшей общей подпоследовательности, которая находит наибольшую общую подпоследовательность среди двух строк так, что она также является палиндромом.

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Задача_о_наибольшей_общей_подпоследовательности-палиндроме&oldid=41487»