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 \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>, если входит, то вернем добавим этот символв ответ, если нет - вернем пустую строку. Таким образом ответом , в результате работы алгоритма соберем последовательность, которая будет конкатенация являться искомой. === Псевдокод === В данном примере <tex> x, y </tex> - последовательности, <tex> ans </tex> - вектор ответа. <tex> LCS </tex> - функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех вызовов функциипрефиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, как скрытую передачу границ для хранящихся глобально данных. '''void''' hirschberg(x: '''vector''', y: '''vector'''): '''if''' x.size() == 1 '''if''' y.contains(x[0]) ans.push(x[0]) ''<font color="green"> // сохранение очередного элемента lcs </font>'' return mid = x.size() / 2 vector f = LCS(x[0 .. mid], y) vector s = LCS(reverse(x[mid + 1 .. x.size()]), reverse(y)) max = s[0] ''<font color="green"> // s[0] подразумевает, что это lcs для второй половины x и всей последовательности y </font>'' it_max = 0 '''for''' j = 0 '''to''' y.size() '''if''' f[j] + s[j + 1] > max max = f[j] + s[j + 1] it_max = j '''if''' f[y.size() - 1] > max it_max = y.size() - 1 delete[] f delete[] s ''<font color="green"> // промежуточные массивы необходимо удалять или хранить глобально </font>'' hirschberg(x[0 .. mid], y[0 .. it_max]) hirschberg(x[mid + 1 .. x.size()], y[it_max .. y.size()])
== См. также ==
