Longest common subsequence (LCS)

Albert Davletov
UniLecs
Published in
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.

Пример заполнения массива для строки «abcabaac» и «baccbca».

Однако, это решение находит только длину наибольшей общей подпоследовательности. Для нахождения самой общей подпоследовательности необходимо восстановить ответ. Для этого выполним «обратный проход» по массиву 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].

Реализация

C++

https://gist.github.com/unilecs/dc25ef4b19feeac1404da670f6d4548e

Play-test

https://repl.it/@unilecs/MaxSubsequenceC

Python

https://gist.github.com/unilecs/1067f7be239bb45128afe78bf76e9365

Play-test

https://repl.it/@unilecs/maxSubsequence

--

--