16
правок
Изменения
Нет описания правки
{{Определение
|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>.
}}
== Постановка задачи ==
== Наивная идея решения ==
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая НОП LCS гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
=== Построение подпоследовательности ===
Для каждой пары элементов помимо длины НОП LCS соответствующих префиксов хранятся и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность.
=== Псевдокод ===
