Longest common subsequence (LCS)

Published in

UniLecs

3 min readDec 11, 2019

Подпоследовательность строки — это некоторое подмножество символов исходной строки, следующих в том же порядке, в котором они идут в исходной строке, но не обязательно подряд. Пустая подпоследовательность не содержит ни одного элемента и также является подпоследовательностью строки.

Задача — для двух данных строк найти такую строку наибольшей длины, которая была бы подпоследовательностью каждой из них.

Пусть 1я строка состоит из n символов a[0]…a[n−1], 2я строка состоит из m символов b[0]…b[m−1].

Например, если A = «abcabaac», B = «baccbca» то у строк A и B есть общая подпоследовательность длины 4, например, «acba» или «acbc».

Разбор

Рассмотрим последние символы данных строк A[n−1] и B[m−1]. Если эти символы совпадают, то они обязательно войдут последними символами и в наибольшую общую подпоследовательность этих строк. Тогда можно свести задачу нахождения наибольшей общей подпоследовательности для строк A=a[0]…a[n−1] и B=b[0]…b[m−1] к задаче нахождения наибольшей общей подпоследовательности для строк, полученных отбрасыванием от данных строк последнего символа, то есть для a[0]…a[n−2] и b[0]…b[m−2]. Затем к ответу для «укороченных» строк добавим последние (равные) символы исходных строк (a[n−1] или b[m−1]) и получим ответ для исходных строк.

Если же последние символы исходных строк не совпадают, то эти символы (a[n−1] и b[m−1]) не могут одновременно входить в наибольшую общую подпоследовательность, поэтому можно один из них отбросить. Тогда задача сводится к нахождению наибольшей общей подпоследовательности для одного из двух случаев — для строк a[0]…a[n−2] и b[0]…b[m−1](«abcabaa» и «baccbca») или для строк a[0]…a[n−1] и b[0]…b[m−2](«abcabaac» и «baccbc»).

Таким образом, мы можем сводить задачу нахождения наибольшей общей подпоследовательности двух строк к меньшей задаче — нахождения наибольшей общей подпоследовательности для строк, полученных отбрасыванием последних символов от исходных строк (префиксов исходных строк). А дальше нам помогут принципы построения решения при помощи динамического программирования.

Рассмотрим префикс A′ первой строки из i символов: A′=a[0]…a[i−1] и префикс B′ второй строки из j символов: B′=b[0]…b[j−1]. Обозначим через F(i, j) длину наибольшей общей подпоследовательности
для A′ и B′.

Теперь найдем формулы для динамического программирования (рекуррентные соотношения). Они зависят от того, совпадают ли последние символы рассматриваемых строк A′ и B′. Если a[i−1]=b[j−1], то тогда F(i, j)=F(i−1, j−1)+1 — нужно решить задачу для строк, полученных отбрасыванием последних символов рассматриваемых строк и добавить 1 символ к ответу. В противном случае нужно рассмотреть два случая: F(i−1, j) и F(i, j−1), которые соответствуют отбрасыванию по одному символу от конца каждой из рассматриваемых строк. В этом случае F(i,j)=max(F(i−1, j),(i, j−1)).
Начальные значения функции F задаются просто: если одна из строк — пустая, то общая подпоследовательность также пустая, то есть имеет длину 0: F(0, j)=F(i,0)=0.

Далее необходимо завести двумерный массив размером (n+1)×(m+1) и заполнить его значениями по указанным рекуррентным соотношениям. Сначала весь массив заполним нулями (что даст нам граничные значения), затем двумя вложенными циклами по i и по j заполним оставшуюся часть массива.

Пример заполнения массива для строки «abcabaac» и «baccbca». Длина наибольшей общей подпоследовательности для данных строк равна 4.

Однако, это решение находит только длину наибольшей общей подпоследовательности. Для нахождения самой общей подпоследовательности необходимо восстановить ответ. Для этого выполним «обратный проход» по массиву F начиная с последнего элемента. В каждой рассматриваемой ячейке F[i][j] выясним, как было получено значение в этой ячейке. Это зависит от последних символов рассматриваемых префиксов. Если a[i−1]=b[j−1], то тогда ответ для элемента F[i][j] получен из F[i−1][j−1]добавлением 1, поэтому перейдем к элементу F[i−1][j−1], а к ответу добавим символ a[i−1]=b[j−1]. Иначе нужно перейти к тому элементу F[i−1][j] или F[i][j−1], значение в котором совпадает со значением F[i][j].