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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Задача о '''наибольшей общей подпоследовательности-палиндрома''' (англ. ''longest common subsequence'') ...»)
(нет различий)

Версия 16:43, 29 ноября 2014

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

Определения

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


Определение:
Подпоследовательностью-палиндромом данной строки называется последовательность символов из данной строки, не обязательно идущих подряд, являющаяся палиндромом.


Определение:
Последовательность [math] Z [/math] является общей подпоследовательностью (англ. common subsequence) последовательностей [math] X [/math] и [math] Y [/math], если [math] Z [/math] является подпоследовательностью как [math] X [/math], так и [math] Y [/math].

Например, HELOLEH является подпоследовательностью-палиндромом строки HTEOLFEOLEH.