Пошук найдовшої спільної підпослідовності

Пошук найдовшої спільної підпослідовності (англ. longest common subsequence, LCS) — це завдання пошуку послідовності, яка є підпослідовністю кількох послідовностей (зазвичай — двох). Часто завдання визначається як пошук всіх найбільших спільних підпослідовностей. Ця задача відрізняється від пошуку найдовшого спільного підрядка: на відміну від підрядків, підпослідовності не повинні займати суміжні позиції в оригінальних послідовностях. Це класична задача інформатики, яка має застосування, зокрема, в задачі порівняння текстових файлів (утиліта diff), а також у біоінформатиці.

Підпослідовність можна отримати з деякої послідовності, якщо видалити з неї деяку множину елементів (можливо, порожню). Наприклад, BCDB є підпослідовністю послідовності ABCDBAB. Також вона буде підпослідовністю послідовності XBXCDXBX. Послідовність Z є спільною підпослідовність послідовностей X і Y, якщо Z є підпослідовністю як X, так і Y. Потрібно для двох послідовностей X і Y знайти спільну підпослідовність найбільшої довжини. Зауважимо, що таких підпослідовностей може бути кілька.

Вирішення задачі[ред. | ред. код]

Порівняємо два методи рішення: повний перебір і динамічне програмування.

Повний перебір[ред. | ред. код]

Існують різні підходи при вирішенні даної задачі. Один з них — повний перебір. Ми порівнюємо кожен елемент рядка X з кожним елементом рядка Y, тобто ${\displaystyle 2^{n}}$ — час роботи такого алгоритму.

Метод динамічного програмування[ред. | ред. код]

Спочатку знайдемо довжину найбільшої підпослідовності. Припустимо, ми шукаємо рішення для випадку (n₁, n₂), де n₁, n₂ — довжина першого та другого рядків. Нехай вже існують рішення для всіх підзадач (m₁, m₂), менших заданої. Тоді задача (n₁, n₂) зводиться до підзадач наступним чином:

${\displaystyle f(n_{1},n_{2})=\left\{{\begin{array}{ll}0,&n_{1}=0\lor n_{2}=0\\f(n_{1}-1,n_{2}-1)+1,&s[n_{1}]=s[n_{2}]\\max(f(n_{1}-1,n_{2}),f(n_{1},n_{2}-1)),&s[n_{1}]\neq s[n_{2}]\end{array}}\right.}$

Тепер повернемося до задачі побудови підпослідовності. Для цього в наявний алгоритм для кожної задачі додають запам'ятовування тих підзадач, через які вона вирішується. Наступною дією, починаючи з останнього елемента, піднімаємося до початку за напрямками, заданим першим алгоритмом, і записуємо символи в кожній позиції. Це і буде відповіддю в цій задачі.

Очевидно, що час роботи алгоритму буде ${\displaystyle \mathrm {O} \,(n_{1}\cdot n_{2})}$^{[джерело?]}.

Реалізація алгоритму[ред. | ред. код]

С++[ред. | ред. код]

    string getLongestCommonSubsequence(const string& a, const string& b)     {         vector<vector<int> > max_len;         max_len.resize(a.size() + 1);         for(int i = 0; i <= static_cast<int>(a.size()); i++)             max_len[i].resize(b.size() + 1);         for(int i = static_cast<int>(a.size()) - 1; i >= 0; i--)         {             for(int j = static_cast<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 < static_cast<int>(a.size()) && j < static_cast<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;     } 

Ruby[ред. | ред. код]

#>> a = "aaaaabbbb34354354345" #>> b = "abbb34aaabbbb" #>> longest_common_subsequence(a, b) #=> "aaaabbbb"   def longest_common_subsequence(a, b)     max_len = Array.new(a.size + 1, 0)     max_len.map! {Array.new(b.size + 1, 0)}      (a.size - 1).downto(0) do |i|       (b.size - 1).downto(0) do |j|         if a[i] == b[j]           max_len[i][j] = 1 + max_len[i+1][j+1]         else           max_len[i][j] = [max_len[i+1][j], max_len[i][j+1]].max         end       end     end      res = ""     i = 0     j = 0     while max_len[i][j] != 0 && i < a.size && j < b.size       if a[i] == b[j]         res << a[i]         i += 1         j += 1       else         if max_len[i][j] == max_len[i+1][j]           i += 1         else           j += 1         end       end     end      res   end 

Примітки[ред. | ред. код]