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

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

Вирішення задачі

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

Повний перебір

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

Метод динамічного програмування

A B C B 0 0 0 0 0 D   0 ← 0 ← 0 ← 0 ← 0 C   0 ← 0← 0↖ 1 ← 1 B   0 ← 0 ↖ 1 ← 1 ↖ 2 A   0 ↖ 1 ← 1 ← 1 ↑ 2

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

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

Очевидно, що час роботи алгоритму буде .

Реалізація алгоритму

С++

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

Python def lcs(a, b): n, m = len(a) + 1, len(b) + 1 f = [ * m for i in range(n)] for i in range(1, n): for j in range(1, m): f[i][j] = f[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(f[i-1][j], f[i][j-1])

i, j = len(a), len(b) res = '' while f[i][j] > 0: if f[i][j] == f[i][j-1]: j -= 1 elif f[i][j] == f[i-1][j]: i -= 1 else: res = a[i-1] + res i -= 1 j -= 1 return res

Джерела

Примітки