3622
правки
Изменения
м
→Наивная идея решения
Даны две последовательности: <tex> X = \left \langle x_1, x_2, ..., x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, ..., y_n \right \rangle </tex>. Требуется найти общую подпоследовательность <tex> X </tex> и <tex> Y </tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.
== Наивная идея решения Наивное решение ==
Переберем все различные подпоследовательности обеих строк и сравним их. Тогда искомая LCS гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
