10
правок
Изменения
м
→Алгоритм
Не теряя общности, будем считать, что <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 + 1 \dots n \right ])) \right | = max </tex> . Запустим алгоритм рекурсивно для пар <tex>(x^1, y \left [0 \dots j \right ])</tex> и <tex>(x^2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно 1 элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то добавим этот символ в ответ, если нет - вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.
=== Псевдокод ===
