Изменения

Не теряя общности, будем считать, что <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> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>, часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связанысо второй половиной <tex> x </tex>, лежат правее <tex> y_i </tex>, в противном случае, либо <tex> y_i </tex> не состоит в паре с <tex> x_i </tex>, либо <tex> x_i </tex> не последний символ из <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </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> 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> lcs m + n + \min (m, n) </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбиратьпамяти. Тогда рассмотрим разделение Дополнительно на две части каждом шаге рекурсии вызываются <tex>X2</tex>, часть символов LCS (возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <tex> x_i функции </tex> последний символ из LCS в первой половине, тогда наш алгоритм выберет соответствующий ему <tex> y_i </tex> в качестве точки разделения. То есть символы из <tex> y </tex>, которые связанысо второй половиной суммарно требуют <tex> x 4k_i </tex>, лежат правее где <tex> y_i k_i </tex>, в противном случае, либо — длина части <tex> y_i y </tex> не состоит в паре с <tex> x_i </tex>текущий момент, либо так как для нахождения <tex> x_i LCS </tex> не последний символ из достаточно двух строк матрицы <tex> lcs </tex> в первой половине. Заметим, что если первая половина не содержит <tex> lcs </tex>, то точки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>Вспомогательные массивы удаляются перед рекурсивным вызовом, которая включается в первую половину. Таким таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X </tex> останется 1 символобщие затраты равны сумме размеров массивов на одной глубине рекурсии, то возможны два варинта, либоон входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, что на каком-то шаге, вся подпоследовательность оказалась в одной из половин <tex> X </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>

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