Самая длинная общая подпоследовательность
- Самая длинная общая подпоследовательность (LCS) — это самая длинная подпоследовательность, общая для всех последовательностей в наборе последовательностей.
- Задача вычисления LCS является классической задачей информатики и имеет применение в компьютерной лингвистике, биоинформатике и системах контроля версий.
- Сложность задачи LCS является NP-сложной для общего случая с произвольным числом входных последовательностей.
- Для двух последовательностей из n и m элементов время выполнения подхода динамического программирования равно O(n × m).
- Существуют методы с меньшей сложностью, которые часто зависят от длины LCS, размера алфавита или от того и другого вместе.
- LCS не обязательно уникальна, и алгоритмическая сложность должна быть как минимум экспоненциальной.
- Решение для двух последовательностей может быть разбито на более мелкие, простые подзадачи, которые могут быть решены с помощью динамического программирования.
Полный текст статьи: