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

Материал из Википедии — свободной энциклопедии

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

[править] Решение задачи

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

Нахождение наибольшей общей подпоследовательности является одной из классических задач динамического программирования. Приведённая ниже реализация алгоритма имеет сложность 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; )
       {
           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;
   }