418
правок
Изменения
Нет описания правки
=== Решение ===
Обозначим как <tex> a[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получаем следующее рекуррентное соотношение:
<tex>
a[i][j] =
\begin{cases}
a[i - 1][j - 1] + 1, & \text{если }x[i] = y[j]\text{ (соответствующие элементы последовательностей равны); } \\ max(a[i][j - 1], a[i - 1][j]), & \text{если }x[i] \neq y[j]\text{ (соответствующие элементы последовательностей не равны).}
\end{cases}
</tex>
Очевидно, что сложность алгоритма составит <tex> O(n^2) </tex>.
