ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 109
Скачиваний: 1
Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.
Метод динамического программирования[]
|
|
A |
B |
C |
B |
|
0 |
0 |
0 |
0 |
0 |
D |
0 |
← 0 |
← 0 |
← 0 |
← 0 |
C |
0 |
← 0 |
← 0 |
↖ 1 |
← 1 |
B |
0 |
← 0 |
↖ 1 |
← 1 |
↖ 2 |
A |
0 |
↖ 1 |
← 1 |
← 1 |
↑ 2 |
Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.