16
правок
Изменения
Нет описания правки
0, & i = 0\text{ or }j = 0 \\
lcs[i - 1][j - 1] + 1, & x[i] = y[j] \\
\max(lcs[i][j - 1], lcs[i - 1][j]), & x[i] \neq y[j]
\end{cases}
</tex>
|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_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>
}}
Наивное решение подсчёта <tex>LCS </tex> нескольких строк при помощи последовательного нахождения <tex>LCS </tex> двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.
Даны три последовательности:
}}
===Решение===
Обозначим как <tex> lcs[i][j][l] </tex> <tex>LCS</tex> Наибольшую общую подпоследовательность префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение:
<tex>
0, & i = 0\text{ or }j = 0\text{ or }l = 0 \\
lcs[i - 1][j - 1][l - 1] + 1, & x[i] = y[j] = z[l] \\
\max(lcs[i][j - 1][l], lcs[i - 1][j][l], lcs[i][j][l - 1]), & x[i] \neq y[j] \neq z[l]
\end{cases}
</tex>
Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </tex> и <tex> k </tex> — длины последовательностей.
Аналогичным образом задача решается для <tex>k </tex> строк. Заполняется <tex>k</tex>-мерная динамика.
== См. также ==
*[[Задача о наибольшей возрастающей подпоследовательности]]
