Найбольшая агульная падпаслядоўнасць

Задача знаходжання найбольшай агульнай падпаслядоўнасці (англ.: longest common subsequence, LCS) — задача пошуку паслядоўнасці, якая з'яўляецца падпаслядоўнасцю некалькіх паслядоўнасцяў (звычайна дзвюх). Часта задача вызначаецца як пошук усіх найбольшых падпаслядоўнасцяў. Гэта класічная задача інфарматыкі, якая мае ўжыванне, у прыватнасці, у задачы параўнання тэкставых файлаў (утыліта diff), а таксама ў біяінфарматыцы.

Падпаслядоўнасць можна атрымаць з некаторай канчатковай паслядоўнасці, калі выдаліць з апошняй некаторае мноства яе элементаў (магчыма пустое). Напрыклад, BCDB з'яўляецца падпаслядоўнасцю з ABCDBAB. Будзем лічыць, што паслядоўнасць Z з'яўляецца агульнай падпаслядоўнасцю паслядоўнасцяў X і Y, калі Z з'яўляецца падпаслядоўнасцю як 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

Спачатку знойдзем даўжыню найбольшай падпаслядоўнасці. Дапусцім, мы шукаем рашэнне для выпадку (n₁, n₂), дзе n₁, n₂ — даўжыні першага і другога радка. Хай ужо існуюць рашэнні для усіх падзадач (m₁, m₂), меншых зададзенай. Тады задача (n₁, n₂) зводзіцца да меншых падзадач наступным чынам:

$f(n_1, n_2) = \left \{ \begin{array}{ll} 0, & n_1 = 0 \or n_2 = 0 \\ f(n_1 - 1, n_2 - 1) + 1, & s[n_1] = s[n_2] \\ max(f(n_1 - 1, n_2), f(n_1, n_2 - 1)), & s[n_1] \neq s[n_2] \end{array} \right.$

Зараз вернемся да задачы будавання падпаслядоўнасці. Для гэтага ў існуючы алгарытм дададзім запамінанне для кожнай задачы той падзадачы, праз якую яна вырашаецца. Наступным дзеяннем, пачынаючы з апошняга элемента, падымаемся да пачатку па напрамкам, зададзеным першым алгарытмам, і запісваем сімвалы ў кожнай пазіцыі. Гэта і будзе адказам у дадзенай задачы.

Час працы алгарытму будзе $\mathrm{O}\,(n_1 \cdot n_2)$.