Наибольшая общая подпоследовательность

Пусть даны две последовательности чисел (символов) $a_{1}, \ldots, a_{n}$ и $b_{1}, \ldots, b_{m}$. Требуется найти последовательность $c$ как можно большей длины, которая была бы подпоследовательностью и $a$, и $b$. Например, для последовательностей $2,1,2,3,1,2$ и $2,3,2,2,1$ возможные ответы $-2,2,2 ; 2,3,2 ; 2,3,1$ и $2,2,1$.

Пусть $l[i, j]$ - длина наибольшей общей последовательности (НОП, longest common subsequence, LCS) последовательностей $a_{1}, \ldots, a_{i}$ и $b_{1}, \ldots, b_{j}$. Начальные значения: $l[i, 0]=$ $l[0, j]=0$. Нас интересует $l[n, m]$.

Как вычислить $l[i, j]$ ? Посмотрим на $a_{i}$ и $b_{j}$ : либо один из них не входит в ответ (то есть $l[i, j]=l[i-1, j]$ или $l[i, j]=l[i, j-1]$ ), либо они оба совпадают с последним элементом ответа, тогда $l[i, j]=l[i-1, j-1]+1$. Последний случай возможен лишь при $a_{i}=b_{j}$. Поскольку нас интересует наибольшая общая подпоследовательность, нужно взять максимум по всем возможным переходам. Заметим, что если мы будем перебирать состояния в порядке увеличения $i$, а потом $j$, то к моменту рассмотрения состояния $(i, j)$ состояния $(i-1, j),(i, j-1)$ и $(i-1, j-1)$ уже будут рассмотрены. Получаем решение за $O(n m)$.

1
2
3
4
5
6

fill(l, 0)
for i = 1..n:
    for j = 1..m:
        l[i, j] = max(l[i - 1, j], l[i, j - 1])
        if a[i] == b[j]:
            l[i, j] = max(l[i, j], l[i - 1, j - 1] + 1)

Значения $l$ для последовательностей $2,1,2,3,1,2$ и $2,3,2,2,1$ представлены в таблице:

Восстановление ответа

Пусть требуется узнать не только длину НОП, но и найти саму подпоследовательность. Как мы уже обсуждали, это делается любым из двух способов: можно запомнить для каждого состояния, какой из переходов в него был оптимальным, а можно ничего не запоминать, а находить оптимальный переход по мере надобности, перебирая все переходы заново. Так

или иначе, будем откатываться из конечного состояния ( $n, m$ ), переходя по оптимальным переходам и добавляя символ в ответ, когда переход идёт “по диагонали”. Остановимся, когда придём в одно из начальных состояний. Приведём для разнообразия реализацию второго способа.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

i = n, j = m
while i > 0 and j > 0:
    if a[i] == b[j] and l[i, j] == l[i - 1, j - 1] + 1:
        ans.push_back(a[i])
        i -=1, j -= 1
    else if l[i, j] == l[i - 1, j]:
        i -= 1
    else: # l[i, j] == l[i, j - 1]
        j -= 1
reverse(ans.begin(), ans.end())

Оптимизация памяти

Пусть нас интересует только длина НОП, тогда можно обойтись $O(\min (m, n))$ дополнительной памяти. Для этого заметим, что при вычислении $i$-й строки таблицы состояний мы используем только $i$-ю и ( $i-1$ )-ю строки. Значит, все предыдущие строки можно уже не хранить - получаем решение с $O(m)$ памяти. Остаётся заметить, что последовательности всегда можно поменять местами, поэтому хватит и $O(\min (m, n))$ памяти.

int l[2][m + 1]
fill(l, 0)
for i = 1..n:
    cur = i % 2, prev = 1 - cur
    for j = 1..m:
        l[cur, j] = max(l[prev, j], l[cur, j - 1])
        if a[i] == b[j]:
            l[cur, j] = max(l[cur, j], l[prev, j - 1] + 1)