== Описание алгоритма ==
=== Предподсчёт ===Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности ]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex> (n + 1) \times (n + 1) </tex>. Разобьём её на квадраты размера <tex> k \times k </tex> следующим образом: выделим каждую <tex> k + 1 </tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.
[[Файл:Table_4russiansТребуется, чтобы <tex> k </tex> делило <tex> n </tex>, но это не является ограничением - можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя <tex> k </tex>.GIF]]
Требуется, чтобы <tex> k </tex> делило <tex> n </tex>, но это не является ограничением - можно дописать Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в конец последовательностей символыверхнем левом «уголке» над квадратом и подстрок, которые не встречались для которых считается ответ — остальные значения в других местах этих последовательностей (символы для каждой последовательности должны быть разными)квадрате однозначно считаются с их помощью. Тогда ответ на задачу не изменится, а длину можно "довести" до делителя <tex> k </tex>Окончательным результатом будут значения в нижнем правом «уголке» квадрата.
Сделаем предподсчёт действия каждого возможного квадратаМожет показаться, что таких уголков может быть много. Окончательный Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от значений константы в верхнем левом "уголке" элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex> k - 1 </tex> бит кодирует возрастание чисел в верхнем крае квадрата и подстрок(0 - элемент равен предыдущему, 1 - больше предыдущего на один), для которых считается ответ — остальные значения потом <tex> k - 1 </tex> бит кодируют возрастание чисел в квадрате однозначно считаются с их помощьюпо левому краю аналогичным образом. Окончательным результатом будут значения Более того, константу в нижнем правом "уголке" верхнем левом элементе квадратаможно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата. Посчитаем эти квадраты для строк abbabb и bababb. Возьмём <tex> k = 3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так: [[Файл:4 russians lcs precalc.png]]
Может показаться, что таких уголков может быть много. Но, так как соседние числа в === Вычисление НОП на сжатой матрице отличаются не более, чем на один===Ответ для самой задачи НОП считается аналогично обычному алгоритму, то результат зависит только от константы в верхнем левом элементе матрицырассматривая не каждую ячейку таблицы, и возрастания чисел а квадраты <tex> k \times k </tex>. В очередной квадрат (пусть его левый верхний угол находится в верхнем и левом крае квадрата. Возрастание чисел будем хранить ячейке с помощью битовых масок: сначала координатами <tex> k - 1 i, j </tex> бит кодирует возрастание чисел ) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в верхнем крае квадрата (0 - элемент равен предыдущемуквадрате число, 1 - больше предыдущего на один)стоящее в уголке над квадратом, потом т.е. в ячейке с координатами <tex> k i - 1, j - 1 </tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.
Более того, константу в верхнем левом элементе квадрата можно вообще не хранить - её можно прибавить при необходимости к каждому элементу результата.Для нашего примера итоговая таблица выглядит так:
После этого ответ для самой задачи НОП считается аналогично обычному алгоритму, только на этот раз пересчитывается не каждый элемент матрицы, а только уголки[[Файл:4 russians lcs table.png]]
== Время работы Анализ алгоритма ==
=== Время работы ===
При предподсчёте перебирается <tex> | \Sigma | ^k </tex> (где <tex> | \Sigma | </tex> — мощность алфавита) возможных подстрок первой строки и столько же — второй строки. Для каждой возможной подстроки обеих строк перебирается по <tex> 2^{k - 1} </tex> битовых масок. Для самого предподсчёта требуется время <tex> O(k^2) </tex>. Дальнейший алгоритм поиска НОП требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>. Тогда суммарное время работы алгоритма составляет <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 + \frac{n^2}{k^2} \right ) </tex>.
Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Найдём <tex> k </tex>, решив неравенство:
Пренебрегая <tex> \log k </tex> и <tex> \log 2 </tex> как <tex> o(k) </tex>, получаем <tex> k \leqslant \frac{\log n}{1 + \log | \Sigma |}</tex>
== Используемая память ==
Для каждого предподсчитанного квадрата хранятся подстроки длиной <tex> 2k </tex>, битовые маски длиной <tex> 2k </tex> и результат — нижний «уголок» длины <tex> 2k - 1 </tex>. Как уже было подсчитано, всего предподсчитывается <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} </tex> квадратов. Дальнейший алгоритм требует <tex> O \left ( \frac{n^2}{k^2} \right ) </tex>, значит, всего требуется <tex> O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot (2k + 2k + 2k - 1) + \frac{n^2}{k^2} \right ) = O \left ( |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k + \frac{n^2}{k^2} \right ) </tex> памяти.
== Источники ==
