Довідка та теорія
Найдовша спільна підпослідовність (LCS) двох рядків — це найдовший набір символів, що зустрічається в обох у тому самому порядку, але не обов'язково поруч.
Рекурентність ДП
Нехай L[i][j] — довжина LCS перших
i символів A та перших j B:
L[0][j] = L[i][0] = 0.-
Якщо
A[i] = B[j]:L[i][j] = L[i−1][j−1] + 1(діагональний збіг). -
Інакше
L[i][j] = max(L[i−1][j], L[i][j−1]).
Відновлення підпослідовності
З правого нижнього кута рухайтесь назад: на збігу йдіть по діагоналі й зберігайте символ; інакше крокуйте до більшого сусіда. Розгорніть зібрані символи, щоб отримати LCS.
Складність
Сітка має (m+1)×(n+1) клітинок, тож алгоритм
працює за O(m·n) часу та пам'яті.
Де застосовується
Утиліта diff, контроль версій, порівняння
послідовностей ДНК і виявлення плагіату — усі живляться LCS.
Поширені запитання
Що таке найдовша спільна підпослідовність?
Найдовша спільна підпослідовність (LCS) двох рядків — це найдовша послідовність символів, що з'являється в обох у тому самому порядку, але не обов'язково підряд.
Чим підпослідовність відрізняється від підрядка?
Підрядок — це неперервний відрізок символів, тоді як підпослідовність зберігає початковий порядок, але може пропускати символи. ACE — підпослідовність ABCDE, але не підрядок.
Як сітка ДП розв'язує LCS?
Клітинка L[i][j] містить довжину LCS перших i символів одного рядка та перших j іншого. Якщо символи збігаються, це діагональне значення плюс один; інакше — більше зі значень над клітинкою або ліворуч від неї.
Чому діагональний крок означає збіг?
Діагональний крок одночасно споживає по одному символу з кожного рядка. ДП робить цей крок лише тоді, коли ці два символи рівні, тож кожна діагональ на шляху — це збіглий символ LCS.
Як відновлюється підпослідовність?
Починаючи з правого нижнього кута, ви рухаєтесь назад: на збігу йдете по діагоналі й додаєте символ на початок, інакше рухаєтесь до більшого сусіда. Зібрані символи у зворотному порядку утворюють LCS.
Яка складність за часом?
Заповнення сітки потребує O(m·n) часу та O(m·n) пам'яті для рядків довжиною m і n. Відновлення додає лише O(m+n).
Де LCS застосовується на практиці?
Інструменти diff і системи контролю версій, порівняння послідовностей ДНК і білків, виявлення плагіату та злиття даних — усі спираються на LCS для пошуку спільної структури.
Чи завжди LCS єдина?
Довжина єдина, але максимальної довжини можуть сягати кілька різних підпослідовностей. Показаний тут зворотний хід відновлює одну коректну LCS.
Як LCS пов'язана з відстанню редагування?
Коли дозволені лише вставлення та видалення, відстань редагування дорівнює m + n − 2·LCS. LCS і відстань Левенштейна — тісно пов'язані задачі вирівнювання.
Чи може LCS опрацьовувати більш ніж дві послідовності?
Так, але таблиця ДП отримує вимір на кожну послідовність, тож для довільної кількості послідовностей задача стає NP-складною. Ця симуляція опрацьовує класичний випадок двох рядків.