Построение наибольшей общей подпоследовательности (LCS) на основе наибольшей возрастающей подпоследовательности (LIS)

[Все алгоритмы нахождения LCS]

Данный алгоритм относится к разряду “быстрых” алгоритмов, которые находят LCS двух строк. В среднем случае время работы O(n*log(h)), но в худшем случае все такие “быстрые” алгоритмы вырождаются в O(n*n*log(h)).

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

А теперь по пунктам остановимся на основных моментах.

1) Путь П – это набор из n не обязательно различных целых чисел.

2) Increasing subsequence (IS) of П (Возрастающая подпоследовательность последовательности П) – это набор чисел из П, которые строго увеличиваются при прохождении слева направо.
Пример: 
П = (5,3,4,4,9,6,2,1,8,7,10). 
IS = (3,4,6,8,10), (5,9,10) 

3) Longest increasing subsequence(LIS) of П (Наибольшая возрастающая подпоследовательность последовательности П) – это возрастающая подпоследовательность последовательности П, которая имеет максимальную длину.

4) Decreasing subsequence (DS) of П – невозрастающая подпоследовательность последовательности П при проходе слева направо.
Пример: DS = (5,4,4,2,1)

5) Cover(Покрытие) – множество непересекающихся DS последовательности П, которое содержит все элементы П. Размер покрытия равен количеству DS в покрытии. 
Пример: 
П = (5,3,4,9,6,2,1,8,7)
cover = (5,3,2,1), (4), (9,6), (8,7)

6) Smallest cover (SC) (Наименьшее покрытие) – это покрытие минимального размера

7) Лемма.
Если I – это IS последовательности П, длина которой равна размеру покрытия С последовательности П, тогда I – это LIS последовательности П, а C – SC.
Доказательство леммы смотрите в статье

8) Если П = (5,3,4,9,6,2,1,8,7,10), тогда
D1 = (5,3,2,1),
D2 = (4),
D3 = (9,6),
D4 = (8,7),
D5 = (10),
где D1..D5 – это DS последовательности П, образующие SC.

Процесс построения SC последовательности П основан на жадном алгоритме, при котором последовательно рассматриваются все элементы последовательности П, и затем ищется DS из имеющихся, куда можно добавить в конец рассматриваемый элемент, так, чтобы DS продолжала оставаться DS. При этом имеющиеся DS также просматриваются слева направо. Если возникает ситуация, что текущий элемент не может быть добавлен ни в одну из имеющихся DS, тогда он образует новую – самую левую DS.

9) Лобовая реализация построения SC будет иметь сложность O(N*N). Такая ситуация может возникнуть, если исходная последовательность П является IS.

Сейчас рассмотрим алго со сложностью O(N*log(N)).
П = (5,3,4,9,6,2,1,8,7)

i	П[i]	Хвосты DS (значение хвоста, номер DS)	DS
1	5	(5,1)	D1=(5)
2	3	(3,1)	D1=(5,3)
3	4	(3,1),(4,2)	D1=(5,3)     D2=(4)
4	9	(3,1), (4,2), (9,3)	D1=(5,3)     D2=(4) D3=(9)
5	6	(3,1), (4,2), (6,3)	D1=(5,3)     D2=(4) D3=(9,6)
6	2	(2,1), (4,2), (6,3)	D1=(5,3,2)   D2=(4) D3=(9,6)
7	1	(1,1), (4,2), (6,3)	D1=(5,3,2,1) D2=(4) D3=(9,6)
8	8	(1,1), (4,2), (6,3), (8,4)	D1=(5,3,2,1) D2=(4) D3=(9,6) D4=(8)
9	7	(1,1), (4,2), (6,3), (7,4)	D1=(5,3,2,1) D2=(4) D3=(9,6) D4=(8,7)

Можно заметить что значения хвостов DS представляют собой IS, поэтому при добавлении нового элемента П[i] номер DS, к которому он относится можно не линейно а за O(log(N)), для этого можно использовать модификацию бинарного поиска(lower_bound)

10) Плавно переходим к исходной задаче.
Пусть S1 = “abacx” и S2 = “baabca”.
r(i) – количество вхождений символа S1[i] в строку S2
Тогда:
r(1) = 3, r(2) = 2, r(3) = 3, r(4) = 1, r(5) = 0.
11) Пусть list(x) – список позиций символа x из строки S1 в строке S2 в порядке убывания. Т.е.
list(a) = (6,3,2)
list(b) = (4,1)
list(c) = (5)
list(x) = (empty)

12) Пусть П(S1,S2) – последовательность, полученная путем конкатенации списков list(S1[i]), где i = 1..n.
Для рассматриваемого примера
П(S1, S2) = (6,3,2,4,1,6,3,2,5)

13) Для получения LCS(S1,S2) необходимо найти LIS(П(S1,S2)) из п.12. Элементы, попавшие в этот LIS соответствуют номерам элементов в S2, образующих LCS(S1, S2).

Пример:
LIS = (1,2,5), LCS = bac
LIS = (3,4,6), LCS = aba

Демонстрационное решение: здесь