[Все алгоритмы нахождения LCS] i П[i] Хвосты DS DS
Данный алгоритм относится к разряду “быстрых” алгоритмов, которые находят 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)
(значение хвоста, номер 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
Демонстрационное решение: здесь
