10
правок
Изменения
Добавлена постановка задачи алгоритма Хиршберга и его описание
Аналогичным образом задача решается для <tex>k</tex> строк. Заполняется <tex>k</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>LCS(X,Y)</tex> за время <tex> O(nm) </tex> и <tex> O(\min (n, m)) </tex> памяти.
}}
=== Алгоритм ===
Не теряя общности, будем считать, что <tex> m \ge n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex> x^1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex> x^2 \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для <tex> x^1 </tex> и всех префиксов
последовательности <tex>Y</tex>, аналогично - для развернутых последовательностей <tex> x^2 </tex> и <tex> Y </tex>. Стоит отметить, что для нахождения <tex> LCS </tex> на всех префиксах достаточно одного квадратичного прохода, так как <tex>i</tex>-ый элемент последней строки результирующей матрицы есть не что иное, как <tex> LCS </tex> первой последовательности и префикса второй длины <tex>i</tex>. Затем выберем такой индекс <tex> j </tex>, что <tex> \left | LCS(x^1, y \left [0 \dots j \right ]) + LCS(reverse(x^2), reverse(y \left [j \dots n \right ])) \right | = max </tex> . Запустим алгоритм рекурсивно для пар
<tex>(x^1, y \left [0 \dots j \right ])</tex> и <tex>(x^2, y \left [j \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно 1 элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то вернем этот символ, если нет - вернем пустую строку.
Таким образом ответом будет конкатенация всех вызовов функции.
== См. также ==
