Изменения

Обозначим как <mathtex>a_{i, j}</mathteh> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <mathtex>i</mathtex> и <mathtex>j</mathtex> соответственно.Получаем следующее рекуррентное соотношение:*<mathtex>a_{i, j} = a_{i - 1, j - 1} + 1</mathtex>, если <mathtex>s[i] = s[j]</mathtex> (соответствующие элементы последовательностей равны)*<mathtex>a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})</mathtex>, если <mathtex>s1[i] <> s2[j]</mathtex> (соответствующие элементы последовательностей не равны).Очевидно, что сложность алгоритма составит <mathtex>O(n^2)</mathtex>.

Предположим, что некоторое значение <mathtex>a_{i, j}</mathtex> посчитано неверно. Однако, в случае различия соответствующих символов, они не могут одновременно участвовать в НОП, а значит ответ действительно равен формуле для случая с различными символами. В случае же равенства, ответ не может быть больше, чем <mathtex>a_{i - 1, j - 1} + 1</mathtex>, так как тогда неверно посчитано значение <mathtex>a_{i - 1, j - 1} + 1</mathtex>.

public int[] lcs(int[] s1, int[] s2) {

//Восстановление последовательности int l = return a[s1.length - 1][s2.length - 1]; int[] ans = new int[l]; int ti = s1.length - 1; int tj = s2.length - 1; while (l > 0){ ans[l - 1] = s1[last_1[ti][tj]]; int nti = last_1[ti][tj] - 1; int ntj = last_2[ti][tj] - 1; ti = nti; tj = ntj; l--; } return ans;