Пошук найдовшої спільної підпослідовності — Вікіпедія
Пошук найдовшої спільної підпослідовності (англ. 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; }
#>> 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
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 4.1 Задача пошуку найбільшого підмасиву. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.