Наибольшая общая подпоследовательность
общей подпоследовательности (англ. longest common subsequence, LCS) — задача поиск которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача икоторая имеет приложения, в частности, в задачотличается от подстроки. Например, если есть исходная последовательность «ABCDEF», то «ACE» будет подпоследовательностью, но не подстрокой, а «ABC» будет как подпоследовательностью, так и подстрокой.
Решение задачи[править | править код]
Сравним два метода решения: полный перебор и динамическое программирование.
Полный перебор[править | править код]
Существуют разные подходы при решении данной задачи при полном переборе — можно перебирать варианты подпоследовательности, варианты вычеркивания из данных последовательностей и т. д. Однако в любом случае, время работы программы будет полиномом от длин строк.
Метод динамического программирования[править | править код]
A | B | C | D | ||
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | |
D | 0 | ← 0 | ← 0 | ← 0 | ↖ 1 |
C | 0 | ← 0 | ← 0 | ↖ 1 | ← 1 |
D | 0 | ← 0 | ← 0 | ↑ 1 | ↖ 2 |
A | 0 | ↖ 1 | ← 1 | ← 1 | ↑ 2 |
Вначале найдём длину наибольшей подпоследовательности. Допустим, мы ищем решение для случая (n1, n2), где n1, n2 — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2), меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:
Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента, поднимаемся к началу по направлениям, заданным первым алгоритмом, и записываем символы в каждой позиции. Это и будет ответом в данной задаче.
Время работы алгоритма будет .
См. также[править | править код]
Ссылки[править | править код]
- Нахождение наибольшей общей подпоследовательности . algolist.ru. Дата обращения: 15 августа 2013.
- Алгоритм поиска длины наибольшей общей подпоследовательности . coders.ask-ru.net.
В этой статье не хватает ссылок на источники информации. |
В другом языковом разделе есть более полная статья Longest common subsequence problem (англ.). |