55
правок
Изменения
Новая страница: «Задача о '''наибольшей общей подпоследовательности-палиндрома''' (англ. ''longest common subsequence'') ...»
Задача о '''наибольшей общей подпоследовательности-палиндрома''' (англ. ''longest common subsequence'') — это задача поиска длины наибольшей общей подпоследовательности-палиндрома, которую можно получить вычеркиванием некоторых букв из данных последовательностей.
== Определения ==
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
{{Определение|definition=Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
}}
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
== Определения ==
{{Определение|definition='''Палиндромом''' называется строка, которая одинаково читается как слева направо, так и справа налево.}}
{{Определение|definition='''Подпоследовательностью-палиндромом данной строки''' называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом. }}
{{Определение|definition=Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
}}
'''''Например''''', '''''HELOLEH''''' является подпоследовательностью-палиндромом строки '''''HTEOLFEOLEH'''''.
