Временная сложность
O(m × n)
LCS находит самую длинную подпоследовательность, общую для двух последовательностей. Подпоследовательность — это последовательность элементов, которые идут в том же относительном порядке, но не обязательно расположены подряд.
Как работает (динамическое программирование снизу вверх):
1. Создаётся двумерная таблица: dp[i][j] = длина LCS для первых i символов X и первых j символов Y
2. Если символы совпадают: dp[i][j] = dp[i-1][j-1] + 1
3. Если символы не совпадают: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
4. dp[m][n] содержит длину LCS
Временная сложность: O(m × n)
Пространственная сложность: O(m × n) — можно оптимизировать до O(min(m, n))
Применение:
- Инструменты diff (сравнение файлов)
- Выравнивание последовательностей ДНК
- Системы контроля версий
- Проверка орфографии
LCS — фундаментальная задача биоинформатики и обработки текста. Она обобщается до задачи вычисления расстояния редактирования.
Похожие алгоритмы
Частые вопросы
- Что такое Наибольшая общая подпоследовательность (LCS)?
- LCS находит самую длинную подпоследовательность, общую для двух последовательностей. Подпоследовательность — это последовательность элементов, которые идут в том же относительном порядке, но не обязательно расположены подряд.
- Какова сложность Наибольшая общая подпоследовательность (LCS)?
- Время (среднее): O(m × n) · Память: O(m × n)
- Для кого предназначена визуализация Наибольшая общая подпоследовательность (LCS)?
- Визуализация Наибольшая общая подпоследовательность (LCS) рассчитана на продвинутый уровень в категории «Динамическое программирование». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Наибольшая общая подпоследовательность (LCS)?
- В той же категории (Динамическое программирование) вы можете изучить: Fibonacci DP, Knapsack 0/1. Каждый из них имеет интерактивную визуализацию.