Обозначим как <math>a_{i, j}</math> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <math>i</math> и <math>j</math> соответственно.Получаем следующее рекуррентное соотношение:
*<math>a_{i, j} = a_{i - 1, j - 1} + 1</math>, если <math>s[i] = s[j]</math> (соответствующие элементы последовательностей равны)
*<math>a_{i, j} = max(a_{i, j - 1}, a_{i - 1, j})</math>, если <math>s1[i] <> s2[j]</math> (соответствующие элементы последовательностей не равны).Очевидно, что сложность алгоритма составит <math>O(n^2)</math>.
=== Доказательство оптимальности ===
=== Пример реализации на Java ===
<font size = 3> public int[] lcs(int[] s1, int[] s2) { int[][] a = new int[s1.length][s2.length]; int[][] last_1 = new int[s1.length][s2.length]; int[][] last_2 = new int[s1.length][s2.length]; //Подсчет значений for (int i = 0; i < s1.length; i++) for (int j = 0; j < s2.length; j++) { if (s1[i] == s2[j]) if ((i == 0) || (j == 0)) { a[i][j] = 1; last_1[i][j] = i; last_2[i][j] = j; } else { a[i][j] = a[i - 1][j - 1] + 1; last_1[i][j] = i; last_2[i][j] = j; } else { if ((i > 0) && (a[i - 1][j] > a[i][j])) { a[i][j] = a[i - 1][j]; last_1[i][j] = last_1[i - 1][j]; last_2[i][j] = last_2[i - 1][j]; } if ((j > 0) && (a[i][j - 1] > a[i][j])) { a[i][j] = a[i][j - 1]; last_1[i][j] = last_1[i][j - 1]; last_2[i][j] = last_2[i][j - 1]; }
}
}
//Восстановление последовательности
int l = 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--;
}
//Восстановление последовательности int l = 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; }</font>
