16
правок
Изменения
Нет описания правки
<ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref>
== Решение для случая k строк ==
Найдем решение для 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 \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>
}}
Нельзя подсчитать <tex>V = LCS(X,Y)</tex>, а потом <tex>LCS(V,Z)</tex>. Это легко доказывается контрпримером.
Даны три строки:
<tex>X = \left \langle A, B, C, D, E\right \rangle </tex>
<tex>Y = \left \langle D, E, A, B, C\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 LCS(Z,S3) = \emptyset</tex>
Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex>
{{Теорема
|statement = Пусть имеются последовательности <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> V = \left \langle v_1, v_2, \dots, v_h \right \rangle</tex> — их <tex>LCS</tex>.
# Если <tex>z_k = x_m = y_n</tex>, то <tex>z_k = x_m = y_n = v_h</tex> и <tex> V_{h - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})</tex>
# Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>z_k \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_n,Z_{k - 1})</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>
}}
===Решение===
Обозначим как <tex> lcs[i][j][l] </tex> <tex>LCS</tex> префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение:
<tex>
lcs[i][j][l] =
\begin{cases}
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> — длины последовательностей.
Аналогичным образом задача решается для k строк. Заполняется k-мерная динамика.
== См. также ==
*[[Задача о наибольшей возрастающей подпоследовательности]]
