Изменения

Последовательность <tex> Z = \left \langle z_1, z_2, ...\dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, ...\dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, ...\dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, ...\dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.

Последовательность <tex> Z </tex> является '''общей подпоследовательностью''' (англ. ''common subsequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> Z </tex> является подпоследовательностью как <tex> X </tex>, так и <tex> Y </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>LCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей. == Динамическое программирование == Для решения данной задачи используем [[Динамическое программирование#Принцип оптимальности на префиксе | Принцип оптимальности на префиксе]]. === Доказательство оптимальности ==={{Теорема|statement=Даны две Пусть имеются последовательности: <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> X Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> и — их <tex> Y LCS</tex> максимальной длины. Заметим, что таких подпоследовательностей может быть несколько.

# Если <tex> x_m =y_n </tex>, то <tex> z_k = x_m = y_n </tex> и <tex> Z_{k - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1})</tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq x_m </tex> следует, что <tex> Z </tex> — <tex>LCS(X_{m - 1},Y)</tex># Если <tex> x_m \neq y_n </tex>, то из <tex> z_k \neq y_n </tex> следует, что <tex> Z </tex> — <tex>LCS(X,Y_{n - 1})</tex> |proof=# Если бы выполнялось <tex> z_k \neq x_m </tex>, то к <tex> Z </tex> можно было бы добавить элемент <tex> x_m = y_n </tex>, и тогда получилась бы общая подпоследовательность длины <tex> k + 1 </tex>, что противоречит предположению, что <tex> Z </tex> — <tex>LCS</tex>. Значит, выполняется <tex> z_k = Наивная идея решения x_m =y_n </tex>. Значит, <tex> Z_{k - 1} </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и <tex> Y_{n - 1} </tex>. Докажем от противного, что <tex> Z_{k - 1} </tex> — <tex>LCS</tex>: тогда есть общая подпоследовательность <tex> W </tex>, длина которой больше <tex> k - 1 </tex>. Добавив к <tex> W </tex> элемент <tex> x_m =y_n </tex>, получим <tex>LCS(X,Y)</tex>, длина которой больше <tex> k </tex> (т.е. больше длины <tex> Z </tex>), что приводит к противоречию.Переберем все различные подпоследовательности обеих строк # Если <tex> z_k \neq x_m </tex>, то <tex> Z </tex> — общая подпоследовательность <tex> X_{m - 1} </tex> и сравним <tex> Y </tex>. Пусть существует ихобщая подпоследовательность <tex> W </tex>, длина которой превышает <tex> k </tex>. Мы гарантированно найдем искомую НОПОна также является общей подпоследовательностью <tex> X </tex> и <tex> Y </tex>, однако время работы алгоритма будет экспоненциально зависеть от что противоречит предположению о том, что <tex> Z </tex> (длины исходных последовательностей<tex> k </tex>) — <tex>LCS(X,Y)</tex>.# Аналогично второму случаю.}}

Обозначим как <tex> alcs[i][j] </tex> <tex>LCS</tex> НОП префиксов данных последовательностей, заканчивающихся в элементах с номерами <tex> i </tex> и <tex> j </tex> соответственно. Получаем Получается следующее рекуррентное соотношение:

alcs[i][j] =

alcs[i - 1][j - 1] + 1, & x[i] = y[j] \\ \max(alcs[i][j - 1], a\ lcs[i - 1][j]), & x[i] \neq y[j]

=== Доказательство оптимальности Построение подпоследовательности ===Для каждой пары элементов помимо длины <tex>LCS</tex> соответствующих префиксов хранятся и номера последних элементов, участвующих в этой <tex>LCS</tex>.Таким образом, посчитав ответ, можно восстановить всю наибольшую общую подпоследовательность. === Псевдокод ===<tex> x </tex>, <tex> y </tex> — данные последовательности; <tex> lcs[i][j] </tex> — <tex>LCS</tex> для префикса длины <tex> i </tex> последовательности <tex> x </tex> и префикса длины <tex> j </tex> последовательности <tex> y </tex>; <tex> prev[i][j] </tex> — пара индексов элемента таблицы, соответствующего оптимальному решению вспомогательной задачи, выбранной при вычислении <tex> lcs[i][j] </tex>.  ''<font color="green">// подсчёт таблиц</font>'' '''int''' LCS(x: '''vector''', y: '''vector'''): m = length(x) n = length(y) '''for''' i = 1 '''to''' m lcs[i][0] = 0 '''for''' j = 0 '''to''' n lcs[0][j] = 0 '''for''' i = 1 '''to''' m '''for''' j = 1 '''to''' n '''if''' x[i] == y[j] lcs[i][j] = lcs[i - 1][j - 1] + 1 prev[i][j] = pair(i - 1, j - 1) '''else''' '''if''' lcs[i - 1][j] >= lcs[i][j - 1] lcs[i][j] = lcs[i - 1][j] prev[i][j] = pair(i - 1, j) '''else''' lcs[i][j] =lcs[i][j - 1] prev[i][j] =pair(i, j - 1) ''<font color="green">// вывод LCS, вызывается как printLCS(m, n)</font>''База '''int''' printLCS(i: при '''int''', j: '''int'''): '''if''' i == 0 '''or''' j == 0 ''<font color="green">// пришли к началу LCS</font>'' '''return''' '''if''' prev[i][j] == pair(i - 1, j - 1) ''<font color="green">// если пришли в lcs[i][j] из lcs[i - 1][j - 1], то x[i] == y[j], надо вывести этот элемент</font>'' printLCS(i - 1, j - 1) print x[i] '''else''' '''if''' prev[i][j] == pair(i - 1, j) printLCS(i - 1, j) '''else''' printLCS(i, j - 1) == Оптимизация для вычисления только длины <tex>LCS</tex> ==Заметим, что для вычисления <tex> lcs[i][j] </tex> нужны только <tex> i </tex>-ая и <tex> (i -1) </tex>-ая строчки матрицы <tex> lcs </tex>. Тогда можно использовать лишь <tex> 2 \cdot min(m, n) </tex> элементов таблицы:  '''int''' LCS2(x: '''vector''', y: '''vector'''): '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>'' swap(x, y) m = length(x) n = length(y) '''for''' j = 0 '''to''' n lcs[0][j] = 0 lcs[1][j] = 0 '''for''' i = 1 '''to''' m lcs[1][0] = 0 '''for''' j = 1 '''to''' n lcs[0][j] = lcs[1][j] ''<font color="green">// элемент, который был в a[1][j], теперь в предыдущей строчке</font>'' '''if''' x[i] == y[j] lcs[1][j] = lcs[0][j - 1] + 1 '''else''' '''if''' lcs[0][j] >= lcs[1][j - 1] lcs[1][j] = lcs[0][j] '''else''' lcs[1][j] = lcs[1][j - 1] ''<font color="green">// ответ — lcs[1][n]</font>'' Также можно заметить, что от <tex> или (i - 1) </tex> -ой строчки нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь <tex> min(m, n) </tex> элементов таблицы:  '''int''' LCS3(x: '''vector''', y: '''vector'''): '''if''' length(x) < length(y) ''<font color="green">// в таблице будет length(y) столбцов, и если length(x) меньше, выгоднее поменять местами x и y</font>'' swap(x, y) m = length(x) n = length(y) '''for''' j = 0 '''to''' n lcs[j] = 0 d = 0 ''<font color="green">// d — дополнительная переменная, в ней хранится lcs[i - 1][j - 1]'' ''// в lcs[j], lcs[j + 1], …, lcs[n] хранятся lcs[i - 1][j], lcs[i - 1][j + 1], …, lcs[i - 1][n]'' ''// в lcs[0], lcs[1], …, lcs[j - 1] хранятся lcs[i][0], lcs[i][1], …, lcs[i][j - 1]</font>'' '''for''' i = 1 '''to''' m '''for''' j = 1 '''to''' n tmp = lcs[j] '''if''' x[i] == y[j] lcs[j] = d + 1 '''else''' '''if''' lcs[j] >= lcs[j - 1] lcs[j] = lcs[j] ''<font color="green">// в lcs[j] и так хранится lcs[i - 1][j]</font>'' '''else''' lcs[j] = lcs[j - 1] d = tmp ''<font color="green">// ответ — lcs[n]</font>'' == Длина кратчайшей общей суперпоследовательности ==Для двух подпоследовательностей <tex>X_{m}</tex> и <tex>Y_{n}</tex> длина одной кратчайшей общей суперпоследовательности равна <tex>|SCS(X,Y)| = n + m - |LCS(X,Y)|</tex><ref>[http://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Relation_to_other_problems Wikipedia {{---}} Longest common subsequence problem]</ref> == Решение для случая k строк ==Найдем решение для 3 строк.{{Задача|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>Z = \left \langle z_1, z_2, \dots, z_k \right \rangle</tex>. Необходимо найти <tex>LCS(X,Y,Z)</tex>}}Наивное решение подсчёта <tex>LCS</tex> нескольких строк при помощи последовательного нахождения <tex>LCS</tex> двух строк и уменьшением набора строк на единицу, не срабатывает. Это доказывается следующим контрпримером.Даны три последовательности:  <tex>X = \left \langle A, B, C, D, E\right \rangle </tex> <tex>Y = \left \langle D, E, A, B, C\right \rangle </tex> <tex>Z = \left \langle D, E, F, G, H\right \rangle </tex> Подсчитаем <tex>V = LCS(X,Y) = \left \langle A, B, C \right \rangle</tex> <tex>LCS(Z,V) = \emptyset</tex> Это неверно, так как <tex>LCS(X,Y,Z) = \left \langle D, E \right \rangle</tex> {{Теорема|statement = Пусть имеются последовательности <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> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex>, а <tex> V = \left \langle v_1, v_2, \dots, v_h \right \rangle</tex> — их <tex>LCS</tex>.# Если <tex>z_k = x_m = y_n</tex>, то <tex>z_k = x_m = y_n = v_h</tex> и <tex> V_{h - 1} </tex> — <tex>LCS(X_{m - 1},Y_{n - 1},Z_{k - 1})</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>z_k \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_n,Z_{k - 1})</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>y_n \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_m,Y_{n - 1},Z_k)</tex># Если <tex>z_k \neq x_m \neq y_n</tex>, то из <tex>x_m \neq v_h</tex> следует, что <tex>V</tex> — <tex>LCS(X_{m - 1},Y_n,Z_k)</tex>|proof = Доказательство аналогично доказательству для двух последовательностей.}} ===Решение===Обозначим как <tex> lcs[i][j][l] </tex> наибольшую общую подпоследовательность префиксов данных последовательностей равна нулю, поэтому заканчивающихся в элементах с номерами <tex> i </tex>, <tex> j </tex> и <tex> l </tex> соответственно. Получается следующее рекуррентное соотношение: <tex>lcs[i][j][l] =\begin{cases} 0, & i = 0\text{ or }j = 0\text{ or }l = 0 \\ lcs[i - 1][j - 1][l - 1] + 1, & x[i] = y[j] = z[l] \\ \max(lcs[i][j - 1][l],\ lcs[i - 1][j][l],\ lcs[i][j][l - 1]), & x[i] \neq y[j] \neq z[l]\end{cases}</tex> Очевидно, что сложность алгоритма составит <tex> O(mnk) </tex>, где <tex> m </tex>, <tex> n </tex> и их НОП тоже нулевой <tex> k </tex> — длиныпоследовательностей. Аналогичным образом задача решается для <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(n + m) </tex> памяти.}}

Не теряя общности, будем считать, что <tex> m \geqslant n </tex>. Тогда разобьем последовательность <tex> X </tex> на две равные части <tex dpi="200"> x_1 \left [0 \dots \frac {m} {2} \right ] </tex> и <tex dpi="200"> 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> не только длину НОП соответствующих префиксовостанется ровно <tex>1</tex> элемент, тогда достаточно проверить, входит ли он текущую часть <tex>Y</tex>, но и номера последних элементовесли входит, участвующих то добавим этот символ в этой НОПответ, если нет — вернем пустую строку.Таким образом, посчитав ответв результате работы алгоритма соберем последовательность, мы сможем восстановить всю наибольшую общую подпоследовательностькоторая будет являться искомой.

В данном примере <tex> x, y </tex> — последовательности, <tex> ans </ подсчёт таблиц tex> — вектор ответа. <tex> LCS(X</tex> — функция, возвращающая последнюю строку матрицы <tex> lcs </tex>, для определения ответа на всех префиксах. Важно отметить, что для ее вычисления необходимо и достаточно хранить лишь две соседние строки матрицы <tex> lcs </tex> в любой момент времени. Так как вопрос оптимальности используемой памяти является важным местом данного алгоритма, то передачу различных отрезков последовательностей стоит воспринимать, Y)как скрытую передачу границ для хранящихся глобально данных.   m = length '''void''' hirschberg(Xx: '''vector''', y: '''vector'''): n = length'''if''' y.size(Y) for i <= 1 to m0 a[i][0] = 0return for j '''if''' x.size() = 0 to n a[0][j] = 0 for i = 1 to m for j = 1 to n '''if ''' y.contains(x[i] = y[i] a[i][j] = a[i - 1][j - 1] + 1 b[i][j0] = pair(i - 1, j - 1) else if aans.push(x[i - 1][j] >= a[i][j - 10] a[i][j] = a[i - 1][j] b[i][j] = pair(i - 1, j) else a[i][j] ''<font color= a[i][j - 1] b[i][j] = pair(i, j - 1) "green"> // вывод НОП PrintLCS(b, X, i, j) if i = 0 or j = 0 сохранение очередного элемента lcs <// пришли к началу НОПfont>''

if bmid = x.size() / 2 f[] = LCS(x[i0 .. mid], y) s[j] = pairLCS(i - reverse(x[mid + 1.. x.size()]), j - 1reverse(y)) ''<font color="green">// если пришли в as[i]хранит lcs для второй половины x и суффикса y[ji..y.size()] из a'' ''// это позволяет использовать общий индекс в качестве точки разделения</font>'' max = s[i 0] it_max = - 1 '''for''' j = 0 '''to''' y.size() '''if''' f[j]+ s[y.size() - (j - + 1)], то X> max max = f[ij] = Y+ s[y.size() - (j+ 1)], надо вывести этот элемент PrintLCS it_max = j '''if''' f[y.size(b, X, i ) - 1, j ] > max it_max = y.size() - 1) print X hirschberg(x[0 .. mid], y[i0 .. it_max]) else if bhirschberg(x[imid + 1 .. x.size()], y[jit_max + 1 .. y.size()] ) = pair== Доказательство корректности === Осталось понять, что алгоритм находит нужную подпоследовательность. Не теряя общности, будем считать, что <tex> lcs </tex> единственная, так как нам не важно какую из равных по длине подпоследовательностей выбирать. Тогда рассмотрим разделение на две части <tex>X</tex>, часть символов LCS (i - 1возможно нулевая) попадет в первую половину, оставшаяся — во вторую. Пусть <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>, j)то PrintLCS(bточки разбиения не будет, для симметричного случая со второй половиной точкой разбиения будет <tex> y_i </tex>, которая включается в первую половину. Таким образом, мы свели поиск исходной <tex> lcs </tex> к поиску двух независимых частей. Когда в <tex> X</tex> останется <tex>1</tex> символ, то возможны два варинта, либо он входит в <tex> lcs </tex>, либо нет, в чем мы убеждаемся линейным поиском, случай, когда последний <tex> x </tex> не входит в <tex> lcs </tex>, возникает из-за того, i что на каком- 1то шаге, jвся подпоследовательность оказалась в одной из половин <tex> X </tex>. === Асимптотика ===  Рассмотрим временные затраты алгоритма. Рекурсия представима в виде бинарного дерева высоты не более <tex> \log (m)</tex>, так как она основана на разделении первой последовательности на две равные части на каждом шаге алгоритма. elseОценим время выполнения для произвольной глубины такого дерева и просуммируем результат по всем возможным значениям парметра. На глубине <tex> h </tex> находится <tex> 2^h </tex> вершин с частью последовательности <tex> x </tex> размера <tex dpi = "200">\displaystyle\frac{m}{2^h} </tex> PrintLCS(bи частью <tex> y </tex> длины <tex> k_i </tex>, Xгде сумма семейства <tex> k_i </tex> равна <tex> n </tex>. Таким образом, получаем: * На глубине h: <tex dpi = "200">{\displaystyle \sum_{i, j = 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} = mn \sum_{i = 0}^{\log m}\limits \frac{1}{2^i} < mn \sum_{i = 0}^{\infty}\limits \frac{1}{2^i} = 2mn} </tex>  * Итоговая асимптотика алгоритма: <tex> O(mn)</tex> 

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

LCS2(X, Y) if length(X) * На глубине h: < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y swap(X, Y) m tex dpi = length(X) n = length(Y) for j = 0 to n a[0][j] = 0 a[1][j] = 0 for "200">{\displaystyle\sum_{i = 1 to m a[1][0] = 0 for j = 1 to n a[0][j] = a[1][j] // элемент, который был в a[}^{2^h - 1][j], теперь в предыдущей строчке if x[i] }\limits 4 k_i = y[4 \sum_{i] a[1][j] = a[0][j }^{2^h - 1] + 1 else if a[0][j] >}\limits k_i = a[1][j - 1] a[1][j] = a[0][j] else a[1][j] = a[1][j - 1] 4n} <// ответ — a[1][n]tex>

Приглядевшись повнимательнее, заметим, что от <tex> (i - 1) </tex>-ой строчки нам нужны только элементы с <tex> (j - 1) </tex>-го столбца. В этом случае можно использовать лишь * Итого: <texdpi = "200"> {n + m + \min(m, n) + 4n = O(n + m)}</tex> элементов таблицы:

LCS3(X, Y) if length(X) < length(Y) // в таблице будет length(Y) столбцов, и если length(X) меньше, выгоднее поменять местами X и Y swap(X, Y) m = length(X) n = length(Y) for j = 0 to n a[j] См. также = 0 d = 0 // d — дополнительная переменная, в ней хранится a[i - 1][j - 1] // в a[j], a*[j + 1], …, a[nЗадача о наибольшей возрастающей подпоследовательности] хранятся a[i - 1][j], a[i - 1][j + 1], …, a[i - 1][n] // в a*[0], a[1], …, a[j - 1Наибольшая общая возрастающая подпоследовательность] хранятся a[i][0], a[i][1], …, a[i][j - 1] for i = 1 to m for j = 1 to n tmp = a*[j] if x[iЗадача о наибольшей общей палиндромной подпоследовательности] = y[i] a[j] = d + 1 else if a[j] >= a[j - 1] a[j] = a[j] // в a[j] и так хранится a[i - 1][j] else a[j] Примечания = a[j - 1] d = tmp <references // ответ — a[n]>

Т* Томас Х. Кормен, ЧЧарльз И. Лейзерсон, РРональд Л. РиверстРивест, К. Клиффорд Штайн, «АлгоритмыАлгоритмы: построение и анализ», анализ — 2-е изд.— М.: «Вильямс», стр 418—4252007. — с. 459. — ISBN 5-8489-0857-4* Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequences. Commun. ACM 18, 341–343 (1975) [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]]