Пусть X [1.,,м] и Y [1.,,n] быть двумя данными массивами.Общей супер-последовательностью X и Y является массив Z [1.,,k] так, что X и Y являются подпоследовательностями Z [1.,,к].Цель состоит в том, чтобы найти кратчайшую общую суперпоследовательность (SCS) Z из X и Y, решая следующие подзадачи.
Как показать, что длина k массива Z удовлетворяет уравнению k = m+ n − l, где l - длина самой длинной общей подпоследовательности X и Y?
Требуется использование рекуррентных уравнений и индукции
Ответ довольно логичен, так как я пытался спроектироватьалгоритм нахождения длины СКС.Чтобы найти k of Z, нам нужно найти массив, который имеет подпоследовательности X и Yas и является самым коротким среди всех таких массивов.Если мы уверены, что все элементы в X и Y различны, то мы просто можем суммировать длины X и Y. Однако, X и Y могут иметь общие и повторяющиеся элементы, мы не можем суммировать длины, так как задача состоит в том, чтобы найти самый короткий из возможныхsupersequence.Поэтому нам нужно рассмотреть самую длинную общую подпоследовательность X и Y и отвлечь ее от суммы.
Однако я не знаю, как доказать это с помощью индукции.