Наибольшая общая подпоследовательность — это самая большая последовательность, которая является подпоследовательностью некоторого числа последовательностей.
Введение
Имеются две строки или две числовых последовательности, именуемые А и В. Предположим, что первая строка содержит n знаков а0…аn-1, а вторая строка содержит m знаков b0…bm-1. Подпоследовательностью такой строчки является некое подмножество знаков начальной строки, идущих в такой же очерёдности, как и в исходной строке. Если строка состоит их n знаков, то значит она имеет 2n разных подпоследовательностей, то есть любой из n символов строчки может или быть в составе любой выбранной подпоследовательности или не быть в ней. В пустой подпоследовательности вообще нет элементов, и она может быть подпоследовательностью любых строк.
Наибольшая общая подпоследовательность
Имеется задача со следующими условиями. Требуется для пары заданных строк определить строчку, обладающую максимальными размерами, которая являлась бы подпоследовательностью для каждой. К примеру, заданы строки A=«abcabaac», B=«baccbca», тогда они имеют общую подпоследовательность, длиною в четыре символа. Это: «acba» или «acbc». Эта задача может быть решена при помощи простого перебора. То есть, необходимо перебрать все 2n вариантов подпоследовательностей одной из строк и проверить для всех, входят ли они в число подпоследовательностей другой строки.
Динамическое программирование позволяет упростить решение этой задачи, её сложность при этом составит O(nm). Обозначим последние символы этой пары строк как an−1 и bm−1. В случае совпадения этих символов, они в любом случае должны войти в качестве последних символов также и в самую большую общую подпоследовательность этой пары строчек. В таком случае задача определения максимальной общей подпоследовательности для строчек A=a0…an−1 и B=b0…bm−1 сводится к задаче определения максимальной общей подпоследовательности для строчек, которые получились после отделения от этих строк конечных символов, а именно для a0…an−2 и b0…bm−2. Далее к найденному решению для строк, с уменьшенной на один символ длиной, прибавляются последние символы (которые равны) начальных строчек (an−1 или bm−1), что в итоге даёт искомое решение для начальных строчек. В случае не совпадения последних символов пары исходных строк, знаки an−1 и bm−1 не должны вместе включаться в максимальную общую подпоследовательность, и один из них отбрасывается. При этом, задача может быть сведена к определению максимальной общей подпоследовательности для какого-либо из двух вариантов, то есть для строчек a0…an−2 и b0…bm−1 или для a0…an−1 и b0…bm−2.
На этом примере показано, что можно свести задачу определения максимальной общей подпоследовательности для пары строчек к более простой задаче определения максимальной общей подпоследовательности для строчек, сформированных при отделении от них последних символов. А именно для префиксов начальных строк. Далее рассмотрим решение методом динамического программирования. Префикс A′ одной из строчек, состоящей из i символов, определяется выражением: A′=a0…ai−1. А префикс B′ другой строчки, состоящей из j знаков, равен: B′=b0…bj−1. В обозначениях языка программирования Питон считается, что A′=A[:i] и B′=B[:j]. Введём следующие обозначения. F(i, j) будет длиной максимальной общей подпоследовательности для A′ и B′. Осталось записать рекуррентные соотношения. Они определятся совпадением или его отсутствием для последних символов обрабатываемых строчек A′ и B′. Итоговая программа выглядит следующим образом:
Рисунок 1. Итоговая программа. Автор24 — интернет-биржа студенческих работ
