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