16
правок
Изменения
Нет описания правки
Найдем решение для 3 строк.
{{Задача
|definition = Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex> и <tex>Z = \left \langle z_1, z_2, \dots, z_m z_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>
}}
<tex>X = \left \langle A, B, C, D, E\right \rangle </tex>
<tex>Z = \left \langle D, E, F, G, H\right \rangle </tex>
Подсчитаем <tex>V = LCS(X,Y) = \left \langle A, B, C \right \rangle </tex> <tex>LCS(Z,S3V) = \emptyset</tex>
Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex>
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>y_n \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_{n - 1},Z_k)</tex>
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>x_m \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_{m - 1},Y_n,Z_k)</tex>
|proof = Доказательство аналогично доказательству для двух последовательностей.
}}
===Решение===
Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </tex> и <tex> k </tex> — длины последовательностей.
Аналогичным образом задача решается для k строк. Заполняется <tex>k</tex>-мерная динамика.
== См. также ==
*[[Задача о наибольшей возрастающей подпоследовательности]]
