Изменения

Переберем все различные подпоследовательности обеих строк и сравним их. Мы Тогда искомая НОП гарантированно найдем искомую НОПнайдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.

Данная задача решается с использованием принципа оптимальности на префиксе. Обозначим как <tex> lcs[i][j] </tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получаем Получается следующее рекуррентное соотношение:

Для каждой пары элементов будем хранить не только длину помимо длины НОП соответствующих префиксов, но хранятся и номера последних элементов, участвующих в этой НОП.Таким образом, посчитав ответ, мы сможем можно восстановить всю наибольшую общую подпоследовательность.

Приглядевшись повнимательнее, заметимТакже можно заметить, что от <tex> (i - 1) </tex>-ой строчки нам нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы: