418
правок
Изменения
Нет описания правки
Задача нахождения '''наибольшей общей подпоследовательности''' (''англ.'' '''''longest common subsequence, LCS''''') — это задача поиска последовательности, которая является самой длинной подпоследовательностью нескольких последовательностей (обычно двух).
== Определения ==
{{Определение
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, ..., z_k \right \rangle </tex> является '''подпоследовательностью''' (subsequence) последовательности <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, ..., i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, ..., k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
Другими словами, подпоследовательность данной последовательности — это последовательность, из которой удалили ноль или больше элементов. Например, <tex> Z = \left \langle B, C, D, B \right \rangle </tex> является подпоследовательностью последовательности <tex> X = \left \langle A, B, C, B, D, A, B \right \rangle </tex>, а соответствующая последовательность индексов имеет вид <tex> \left \langle 2, 3, 5, 7 \right \rangle </tex>.
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (common subsequence) последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </tex>.
}}
== Постановка задачи ==
== Наивная идея решения ==
Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
=== Решение ===
Обозначим как <tex>a_{a[i, ][j}] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex>i</tex> и <tex>j</tex> соответственно.Получаем следующее рекуррентное соотношение:*<tex>a_{a[i, ][j} ] = a_\begin{cases} a[i - 1, ][j - 1} ] + 1</tex>, & \text{если <tex>s}x[i] = sy[j]</tex> \text{ (соответствующие элементы последовательностей равны); } \\*<tex>a_{i, j} = max(a_{a[i, ][j - 1}], a_{a[i - 1, ][j}])</tex>, & \text{если <tex>s1}x[i] \neq s2y[j]</tex> \text{ (соответствующие элементы последовательностей не равны).}\end{cases}</tex>Очевидно, что сложность алгоритма составит <tex>O(n^2)</tex>.
=== Доказательство оптимальности ===
Предположим, что некоторое значение <tex>a_{a[i, ][j}] </tex> посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <tex>a_{a[i - 1, ][j - 1} ] + 1</tex>, так как тогда неверно посчитано значение <tex>a_{a[i - 1, ][j - 1} ] + 1</tex>.
=== Построение подпоследовательности ===
