Изменения
Новая страница: «Задача нахождения '''наибольшей общей подпоследовательности''' (''англ.'' '''''longest common subsequence, LC…»
Задача нахождения '''наибольшей общей подпоследовательности''' (''англ.'' '''''longest common subsequence, LCS''''') — это задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух).
== Постановка задачи ==
Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.
== Наивная идея решения ==
Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
== Итого ==
== Спасибо за внимание==
== Постановка задачи ==
Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCDBAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.
== Наивная идея решения ==
Переберем все различные подпоследовательности обеих строк и сравним их. Мы гарантированно найдем искомую НОП, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
== Динамическое программирование ==
== Итого ==
== Спасибо за внимание==
