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