Изменения

Рассмотрим задачу о наибольшей общей подпоследовательности для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex>(n + 1) \times (n + 1)</tex>. Разобьём её на квадраты размера <tex>k \times k</tex> следующим образом: выделим каждую <tex>k</tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы.

Требуется, чтобы <tex>k</tex> делило <tex>n</tex>, но это не является ограничением - можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно "довести" до делителя <tex>k</tex>.

Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом "уголке" квадрата и подстрок, для которых считается ответ {{---}} — остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом "уголке" квадрата.

Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex>k - 1</tex> бит кодирует возрастание чисел в верхнем крае квадрата (0 - элемент равен предыдущему, 1 - больше предыдущего на один), потом <tex>k - 1</tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом.

Суммарное При предподсчёте перебирается <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 (2|\Sigma| ^{2k} \right )}cdot 2^{2k- 2} \cdot k^2 + \frac{n^2}{k^2}\right)</tex>. Понятно, что для получения выигрыша в производительности по сравнению с обычным алгоритмом необходимо, чтобы первое слагаемое не превышало второе. Это достигается при условии Найдём <tex> k </tex>, решив неравенство <tex> |\Sigma| ^{2k} \cdot 2^{2k - 2} \cdot k^2 \leqslant \frac{n^2}{k^2} </tex>. Оно преобразуется к виду <tex> \left ( 2 | \Sigma | \right ) ^{2k} \cdot \frac{1}{4} \cdot k^4 \leqslant n^2 </tex>. Далее извлекаем корень: <tex> \left ( 2 | \Sigma | \right ) ^k \cdot k^2 \leqslant 2n </tex>. Прологарифмируем: <tex> k \log {2 | \Sigma |} + 2 \log k \leqslant \log 2 + \log n </tex>. Отсюда <tex>k < \frac{\log n}{\log {1 + | \log cSigma |}}</tex> == Источники ==* http://pages.cpsc.ucalgary.ca/~pmohasse/private-lcs.pdf