Найдовша загальна підпослідовність: Python, C++ Приклад
⚡ Розумний підсумок
Найдовша спільна підпослідовність визначає найдовший упорядкований шаблон елементів, спільний для двох рядків, без необхідності використання суміжних символів. Цей класичний метод динамічного програмування лежить в основі утиліт diff, вирівнювання ДНК та контролю версій шляхом ефективного порівняння послідовностей за поліноміальний час.

Що таке найдовша спільна підпослідовність?
Найдовша спільна підпослідовність (НСП) означає, що вам буде задано два рядки, шаблони або послідовності об'єктів. Серед цих двох послідовностей або рядків вам потрібно знайти найдовшу підпослідовність елементів в одному порядку, присутню в обох рядках або шаблонах.
Приклад
Наприклад, надано два рядки. Припустимо, що:
Шаблон_1 = “RGBGARGA”
Шаблон_2 = «BGRARG»
- З шаблону pattern_1 можна створювати послідовності типу «RGB», «RGGA», «RGAR». Для створення послідовності потрібно зберегти відносне положення кожного символу в рядку.
- З шаблону pattern_2 ми можемо створювати послідовності типу «BGR», «BRAG», «RARG». Послідовності можна створювати, якщо вони зберігають відносну позицію вихідного рядка.
Термін відносне розташування означає порядок.
Наприклад, «BRG» є коректною послідовністю, оскільки «B» з’явилася першою, потім «R» і лише потім «G» у вихідному рядку pattern_2. Однак, якщо послідовність має вигляд «RBRG», вона некоректна, оскільки у вихідному рядку (pattern_2) «B» йде першою.
У нас є два варіанти пошуку найдовшої спільної підпослідовності з заданих двох послідовностей або масивів.
- Наївний метод
- Рішення для динамічного програмування: найдовша загальна підпослідовність також відома як LCS.
Наївне рішення має більшу часову складність і не є оптимальним рішенням. Використовуючи рішення динамічного програмування (DP), ми долаємо проблему складності.
Наївний метод
Наївний метод — це простий підхід до проблеми, незалежно від часової складності та інших факторів оптимізації. У більшості випадків він складається з «грубої сили», кількох циклів та рекурсивних викликів. Термін «груба сила» означає перебір усіх можливих шаблонів для заданої проблеми.
Приклад
З наведеного вище прикладу pattern1 і pattern2 припустимо, що pattern1 має довжину m, а pattern2 має довжину n. Щоб перевірити всі можливі випадки, нам потрібно оцінити кожну можливу підпослідовність шаблону1 з шаблоном2.
Ось простий рядок із 4 літер «ABCD». Наприклад, нам потрібно створити послідовність з «ABCD». Ми можемо або взяти символ, або ні. Це означає, що для кожного символу у нас є два варіанти:
- Символ буде додано до підпослідовності.
- Символ не буде додано до підпослідовності.
Тут зображення показують усі послідовності, які ми можемо створити з рядка «ABCD».
Послідовність з 1 символу:
Послідовності з 2 символів:
Послідовності з 3 символів:
З наведеної вище діаграми видно 14 послідовностей. Якщо не брати жодної літери, тобто порожній рядок, загальна кількість послідовностей становитиме 15. Більше того, рядок «ABCD» сам по собі є послідовністю. Отже, загальна кількість послідовностей дорівнює 16.
Отже, з «ABCD» можна згенерувати 2^4 або 16 підпослідовностей. Потім рядок довжиною m матиме повну підпослідовність 2^m.
Для кожної підпослідовності нам потрібно перевірити її для всього шаблону2. Це займе O(n) часу. O(n) означає функцію складності, яка обчислює час, необхідний для виконання.
Отже, загальна часова складність стає O(n*2^m). Для прикладу, який ми розглянули вище, значення m=8 та n=5.
Ось кроки наївного методу:
Крок 1) Візьміть послідовність з шаблону1.
Крок 2) Зіставте послідовність з кроку 1 зі шаблоном 2.
Крок 3) Якщо збігається, то збережіть підпослідовність.
Крок 4) Якщо у шаблоні 1 залишилося більше послідовностей, то знову перейдіть до кроку 1.
Крок 5) Вивести найдовшу підпослідовність.
Оптимальна підструктура
Термін «оптимальна підструктура» означає, що оптимальне рішення можна знайти шляхом розв'язання підзадач. Наприклад, у наведеному вище прикладі ми маємо шаблон1 та шаблон2.
Крок 1) Візьміть перші два символи з кожного шаблону.
Крок 2) Візьміть третій-п’ятий символи з кожного шаблону.
Крок 3) Продовжуйте аналогічно з іншими символами.
Рекурсивна структура задачі LCS
Ми знаходимо НСК (довжину НСК) для підрядка (рядка, згенерованого з вихідного рядка). Потім ми ведемо запис довжини НСК підрядків.
Ось ще одна цікава властивість перекриттяping підпроблемиКажуть, що проблема має перекриття.ping підзадачі, якщо постановку задачі можна розбити на невеликі підзадачі та використовувати кілька разів у програмі.
На діаграмі нижче показано, що рекурсивний алгоритм кілька разів викликав функцію з одним і тим же параметром.
Наприклад, розгляньте дерево рекурсії. У темному полі ви можете помітити перекриття.ping підзадачі. («RG», «RA»), («RG», «R») та інші викликаються кілька разів.
Щоб оптимізувати це, ми маємо підхід Динамічне програмування (ДП).
Рекурсивний метод найдовшої спільної підпослідовності
Графік, показаний вище, є рекурсивним методом. Кожна рекурсивна функція має базовий випадок для переривання рекурсії або початку повернення зі свого стеку.
Для цієї реалізації ми використовуватимемо базовий випадок. Отже, алгоритм виглядає наступним чином:
- Якщо всі елементи перед останнім елементом мають збіг, то збільшують довжину на одиницю та повертають.
- Передайте два шаблони до функції та візьміть максимальне значення, яке повертається.
- Якщо один шаблон має нульову довжину, то у нас немає підпослідовності для порівняння. У цьому випадку повертає 0. Це базовий випадок рекурсії.
Псевдо Code:
def lcs: input: pattern_1, pattern_2, len_1, len_2 if len_1 or len_2 is zero: return 0 if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
Реалізація в C++
#include<iostream> #include<bits/stdc++.h> using namespace std; int lcs(string pattern_1, string pattern_2, int len_1, int len_2) { if (len_1 == 0 || len_2 == 0) return 0; if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) { return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1); } else { return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)); } } int main() { string pattern_1, pattern_2; pattern_1 = "RGBGARGA"; pattern_2 = "BGRARG"; cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl; }
вихід:
Length of LCS is: 5
Реалізація в Python
def lcs(pattern_1, pattern_2, len_1, len_2): if len_1 == 0 or len_2 == 0: return 0 if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]: return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1) else: return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1)) pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))
вихід:
Length of LCS is: 5
Метод динамічного програмування найдовшої спільної підпослідовності (LCS)
Динамічне програмування означає оптимізацію простого рекурсивного методу. Наприклад, якщо ми подивимося на граф рекурсивного або наївного підходу, ми можемо побачити, що є кілька однакових викликів функцій. Метод динамічного програмування записує всі обчислення в масив і повторно використовує їх за потреби.
Ми використовуватимемо 2D-масив з розмірами mxn, де m та n – довжини шаблонів pattern1 та pattern2. Для 2D масив, ми можемо використовувати структури даних List у Python або векторні/масивні структури даних у C++.
Псевдо Code для LCS з використанням DP:
LCS(pattern_1, pattern_2): m = length of pattern_1 + 1 n = length of pattern_2 + 1 dp[n][m] for i in range 0 to n + 1: for j in range 0 to m + 1: if i or j equals to 0: dp[i][j] = 0 else if pattern_1[i] == pattern_2[j]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[n][m]
Ось таблична LCS, яка використовується як структура даних 2D-масиву для підходу динамічного програмування.
Давайте обговоримо логіку, яку ми тут використовували. Кроки такі:
Крок 1) Якщо i або j дорівнює нулю, ми беремо порожній рядок з двох заданих рядків і намагаємося знайти спільні підпослідовності. Однак, оскільки підрядок, який ми беремо, порожній, довжина підпослідовності дорівнює 0.
Крок 2) Якщо два символи збігаються, ми присвоїмо значення індексу (i,j), збільшуючи попередньо обчислене НСК, яке присутнє в індексі (i-1,j-1) (з попереднього рядка).
Крок 3) Якщо воно не збігається, то ми візьмемо максимальне значення НСК двох суміжних індексів. Таким чином, нам потрібно заповнити всі значення в 2D-масиві.
Крок 4) Нарешті, ми повернемо значення останньої клітинки 2D-масиву.
По суті, всі значення у 2D-масиві містять довжину спільних підпослідовностей. Серед них остання комірка містить довжину найдовшої спільної підпослідовності.
Реалізація в C++
#include<iostream> using namespace std; int lcs(string pattern_1, string pattern_2) { int m = pattern_1.size(); int n = pattern_2.size(); // dp will store solutions as the iteration goes on int dp[n + 1][m + 1]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < m + 1; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (pattern_2[i - 1] == pattern_1[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; } int main() { string pattern_1 = "RGBGARGA"; string pattern_2 = "BGRARG"; cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl; }
вихід:
Length of LCS: 5
Реалізація в Python
def lcs(pattern_1, pattern_2): m = len(pattern_1) n = len(pattern_2) # dp will store solutions as the iteration goes on dp = [[None] * (n + 1) for item in range(m + 1)] for i in range(m + 1): for j in range(n + 1): if i == 0 or j == 0: dp[i][j] = 0 elif pattern_1[i - 1] == pattern_2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n] pattern_1 = "RGBGARGA" pattern_2 = "BGRARG" print("Length of LCS: ", lcs(pattern_1, pattern_2))
вихід:
Length of LCS: 5
Отже, обидва рядки мають найдовшу спільну підпослідовність довжиною 5.
Коротко кажучи, у методі DP ми просто обчислюємо кожне завдання один раз. У рекурсивному методі може бути перекриття.ping підзадачі.
У цьому алгоритмі динамічного програмування ми використовуємо двовимірну матрицю. Буде подано два рядки (припустимо, що обидва мають довжину n). Тоді необхідний простір у масиві становить nx n. Якщо рядки достатньо великі, нам знадобиться оптимізована для пам’яті версія рішення DP.
Спрощена логіка, яка була використана в коді:
- Оголошення двовимірного масиву DP[m][n].
- Заповніть перший рядок і перший стовпець масиву DP 0.
- Візьміть i та j для ітерації.
- Якщо pattern1[i] дорівнює pattern2[j], тоді оновлюємо DP[i][j] = DP[i-1][j-1] + 1.
- Якщо pattern1[i] не дорівнює pattern2[j], то DP[i][j] буде максимальним значенням між DP[i-1][j] та DP[i][j-1].
- Продовжуйте, доки i та j не досягнуть m та n.
- Останній елемент, DP[m-1][n-1], міститиме довжину.
Тут він адресується як DP[m-1][n-1], оскільки індекс масиву починається з 0.








