Что, если нам нужна сама подпоследовательность, а не ее длина, как раньше ? Заполнив массив L, как показано выше, мы можем ее найти, просто просмативая его. sequence S = empty i = 0 j = 0 while min(i,j) > 0 { if (A[i]==B[j]) { add A[i] to end of S; i--; j--; } else if (L[i+1,j] >= L[i,j+1]) i++; else j++; } Рассмотрим в качестве примера наш предыдущий образец: n e m a t o d e _ k n o w l e d g e e 7 7 6 5 5 5 5 5 4 3 3 3 2 2 2 1 1 1 0 m 6 6 6 5 5 4 4 4 4 3 3 3 2 2 1 1 1 1 0 p 5 5 5 5 5 4 4 4 4 3 3 3 2 2 1 1 1 1 0 t 5 5 5 5 5 4 4 4 4 3 3 3 2 2 1 1 1 1 0 y 4 4 4 4 4 4 4 4 4 3 3 3 2 2 1 1 1 1 0 _ 4 4 4 4 4 4 4 4 4 3 3 3 2 2 1 1 1 1 0 b 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 1 1 1 0 o 3 3 3 3 3 3 3 3 3 3 3 3 2 2 1 1 1 1 0 t 3 3 3 3 3 2 2 2 2 2 2 2 2 2 1 1 1 1 0 t 3 3 3 3 3 2 2 2 2 2 2 2 2 2 1 1 1 1 0 l 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 0 e 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (Вы можете проверить: все вычислено правильно, начиная от низа, и направо ) Чтобы найти наибольшую общую подпоследовательность, посмотрим на первую ячейку L[0,0]. Там 7, значит в последовательности 7 символов. L[0,0] была вычислена как max( L[0,1] , L[1,0] ), которые отвечают подзадачам при удалении "n" из первой строки или "e" из второй. Удаление "n" дает нам подпоследовательность длины L[0,1]=7, в то время как удаление "e" - только L[1,0]=6, так что мы можем удалить лишь "n". Посмотрим на ячейку L[0,1], оcтающуюся после этого удаления. A[0]=B[1]="e", так что мы можем без проблем включить это "e" в подпоследовательность и перейти к L[1,2]=6. Аналогично, это дает "m"... Продолжая в том же духе ( и делая заметки, как в алгоритме выше, двигаясь вниз, а не наискосок ) мы получаем общую подпоследовательность: "emt ole". Итак, мы нашли LCS за время O(mn). Вообще, взглянув на матрицу, можно заметить, что она имеет весьма странную структуру: большие блоки с одинаковыми значениями - и маленькое количесво "углов", где значения меняются. Если это использовать, то можно получить асимптотику O(n log s + c log log min(c,mn/c)), где с - число таких углов, а s - число символов, появляющихся в двух строках.  8  Комментарии к статье  8 8  Обсудить в чате