Наибольшая общая подпоследовательность

Article on other languages:

• Longest_common_subsequence_problem
• Plus_longue_sous-séquence_commune
• 최장_공통_부분_수열
• Najdłuższy_wspólny_podciąg
• 最长公共子序列

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

Задача нахождения наибольшей общей подпоследовательности (англ. longest common subsequence, LCS) — это задача поиска последовательности, которая является подпоследовательностью нескольких последовательностей (обычно двух). Часто задача определяется как поиск всех наибольших подпоследовательностей. Это классическая задача информатики, которая имеет приложения, в частности, в задаче сравнения текстовых файлов (утилита diff), а также в биоинформатике.

Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое). Например, BCDB является подпоследовательностью последовательности ABCBDAB. Будем говорить, что последовательность Z является общей подпоследовательностью последовательностей X и Y, если Z является подпоследовательностью как X, так и Y. Требуется для двух последовательностей X и Y найти общую подпоследовательность наибольшей длины. Заметим, что НОП может быть несколько.

Нахождение наибольшей общей подпоследовательности является одной из классических задач динамического программирования.

Решение задачи

Сравним два метода решения: полный перебор и динамическое программирование.

Полный перебор

Существуют разные подходы при решении данной задачи при полном переборе — можно перебирать варианты подпоследовательности, варианты вычеркивания из данных последовательностей и т. д. Однако в любом случае, время работы программы будет экспонента от длины строки.

Метод динамического программирования

Вначале найдём длину наибольшей подпоследовательности. Допустим мы ищем решение для случая (n₁, n₂), где n₁, n₂ — длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m₁, m₂) меньших заданной. Тогда задача (n₁, n₂) сводится к меньшим подзадачам следующим образом:

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи, той подзадачи, через которую она решается. Следующим действием, начиная с последнего элемента поднимаемся к началу по направлениям, заданным первым алгоритмом и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Очевидно, что время работы алгоритма будет O(n²).

Реализация в языках программирования

C++

string getLongestCommonSubsequence(const string& a, const string& b)
    {
        vector<vector<int> > max_len;
        max_len.resize(a.size() + 1);
        for(int i = 0; i <= (int)a.size(); i++)
            max_len[i].resize(b.size() + 1);
        for(int i = (int)a.size() - 1; i >= 0; i--)
        {
            for(int j = (int)b.size() - 1; j >= 0; j--)
            {
                if(a[i] == b[j])
                {
                    max_len[i][j] = 1 + max_len[i+1][j+1];
                }
                else
                {
                    max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
                }
            }
        }
        string res;
        for(int i = 0, j = 0; max_len[i][j]!=0 && i<(int)a.size() && j<(int)b.size(); )
        {
            if(a[i] == b[j])
            {
                res.push_back(a[i]);
                i++;
                j++;
            }
            else
            {
                if(max_len[i][j] == max_len[i+1][j])
                    i++;
                else
                    j++;
            }
        }
        return res;
    }