Изменения

Не теряя общности, будем считать, что <tex> m \ge geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <texdpi="200"> x^1 x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <texdpi="200"> x^2 x_2 \left [\frac {m} {2} + 1 \dots m \right ] </tex>. Найдем <tex> LCS </tex> для <tex> x^1 x_1 </tex> и всех префиксов последовательности <tex>Y</tex>, аналогично - — для развернутых последовательностей <tex> x^2 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^1x_1, y \left [0 \dots j \right ]) + LCS(reverse(x^2x_2), reverse(y \left [j + 1 \dots n \right ])) \right | = max </tex> . Запустим алгоритм рекурсивно для пар <tex>(x^1x_1, y \left [0 \dots j \right ])</tex> и <tex>(x^2x_2, y \left [j + 1 \dots n \right ])</tex>. Будем продолжать до тех пор, пока в <tex>X</tex> не останется ровно <tex>1 </tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, если входит, то добавим этот символ в ответ, если нет - — вернем пустую строку. Таким образом, в результате работы алгоритма соберем последовательность, которая будет являться искомой.

В данном примере <tex> x, y </tex> - — последовательности, <tex> ans </tex> - — вектор ответа. <tex> LCS </tex> - — функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных.

Оценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера <tex dpi = "200"> \displaystyle\frac{m}{2^h} </tex>

* На глубине h: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{2^h - 1}\limits\frac{m}{2^h} k_i = \frac{m}{2^h} \sum_{i = 0}^{2^h - 1} \limits k_i = \frac{mn}{2^h}} </tex>

* Сумммируем по глубинам: <tex dpi = "200">{\displaystyle \sum_{i = 0}^{\log m}\limits\frac{mn}{2^i} = \frac{mn}{2^h} \sum_{i = 0}^{\log m} \limits \frac{1}{2^i} < \frac{mn}{2^i} \sum_{i = 0}^{\infty} \limits \frac{1}{2^i} = 2mn} </tex>

точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется <tex>1 </tex> символ, то возможны два варинта, либоон входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </tex>.

Проанализируем затраты на память. Три глобальные последовательности (две исходные и одна для ответа), к которым мы обращаемся внутри алгоритма, требуют <tex> m + n + \min (m, n) </tex> памяти. Дополнительно на каждом шаге рекурсии вызываются <tex>2 </tex> функции <tex> LCS </tex>, которые суммарно требуют <tex> 4k_i </tex>, где <tex> k_i </tex> — длина части <tex> y </tex> в текущий момент, так как для нахождения <tex> LCS </tex> достаточно двух строк матрицы <tex> lcs </tex>. Вспомогательные массивы удаляются перед рекурсивным вызовом, таким образом, общие затраты равны сумме размеров массивов на одной глубине рекурсии, то есть:

* На глубине h: <tex dpi = "200">{\displaystyle\sum_{i = 0}^{2^h - 1} \limits 4 k_i = 4 \sum_{i = 0}^{2^h - 1} \limits k_i = 4n} </tex>