18
правок
Изменения
→Предподсчёт: Кажется, опечатка?
== Описание алгоритма == === Предподсчёт ===Рассмотрим [[Задача о наибольшей общей подпоследовательности|задачу о наибольшей общей подпоследовательности]] для двух последовательностей одинаковой длины. Тогда таблица динамического программирования имеет размер <tex> (n + 1) \times (n + 1) </tex>. Разобьём её на квадраты размера <tex> k \times k </tex> следующим образом: выделим каждую <tex> (k + 1) </tex>-ую строчку, начиная с первой. Аналогично выделяем столбцы. Требуется, чтобы <tex> k </tex> делило <tex> n </tex>, но это не является ограничением {{В разработке---}}можно дописать в конец последовательностей символы, которые не встречались в других местах этих последовательностей (символы для каждой последовательности должны быть разными). Тогда ответ на задачу не изменится, а длину можно «довести» до делителя <tex> k </tex>.
Сделаем предподсчёт действия каждого возможного квадрата. Окончательный результат зависит только от значений в верхнем левом «уголке» над квадратом и подстрок, для которых считается ответ {{---}} остальные значения в квадрате однозначно считаются с их помощью. Окончательным результатом будут значения в нижнем правом «уголке» квадрата. Может показаться, что таких уголков может быть много. Но, так как соседние числа в матрице отличаются не более, чем на один, то результат зависит только от константы в верхнем левом элементе матрицы, и возрастания чисел в верхнем и левом крае квадрата. Возрастание чисел будем хранить с помощью битовых масок: сначала <tex> k - 1 </tex> бит кодирует возрастание чисел в верхнем крае квадрата (<tex>0</tex> {{---}} элемент равен предыдущему, <tex>1</tex> {{---}} больше предыдущего на один), потом <tex> k - 1 </tex> бит кодируют возрастание чисел в квадрате по левому краю аналогичным образом. Более того, константу в верхнем левом элементе квадрата можно вообще не хранить: её можно прибавить при необходимости к каждому элементу результата. Посчитаем эти квадраты для строк <tex>abbaba</tex> и <tex>bababb</tex>. Возьмём <tex> k =3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так: {||{|class= Описание алгоритма "wikitable" style="background-color:#FFF; text-align:center; "| colspan="2" rowspan="2" |! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>|-! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>0</tex>|<tex>1</tex>|<tex>1</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|<tex>1</tex>|<tex>1</tex>|<tex>1</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>2</tex>|<tex>2</tex>|}| || || || || || || |{|class="wikitable" style="background-color:#FFF; text-align:center; "| colspan="2" rowspan="2" |! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>|-! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>1</tex>|<tex>1</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|<tex>2</tex>|<tex>2</tex>|<tex>2</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>2</tex>|<tex>3</tex>|<tex>3</tex>|}|} {||{|class="wikitable" style="background-color:#FFF; text-align:center; "| colspan="2" rowspan="2" |! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>|-! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|<tex>1</tex>|<tex>2</tex>|<tex>2</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>2</tex>|<tex>3</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>2</tex>|<tex>3</tex>|}| || || || || || || |{|class="wikitable" style="background-color:#FFF; text-align:center; "| colspan="2" rowspan="2" |! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>|-! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>a</tex>|<tex>1</tex>|<tex>1</tex>|<tex>2</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>1</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>2</tex>|<tex>2</tex>|-! style="background-color:#E0FFFF; width: 40px; height: 40px;" |<tex>0</tex>! style="background-color:#FFEECC; width: 40px; height: 40px;" |<tex>b</tex>|<tex>1</tex>|<tex>2</tex>|<tex>2</tex>|}|} === Вычисление НОП на сжатой матрице ===Ответ для самой задачи НОП считается аналогично обычному алгоритму, только рассматривая не каждую ячейку таблицы, а квадраты <tex> k \times k </tex>. В очередной квадрат (пусть его левый верхний угол находится в ячейке с координатами <tex> i, j </tex>) вставляем значения предподсчитанного квадрата, соответствующего данным подстрокам и битовым маскам, и прибавляем ко всем элементам в квадрате число, стоящее в уголке над квадратом, т.е. в ячейке с координатами <tex> i - 1, j - 1 </tex>. Для нашего примера итоговая таблица выглядит так: {| style=" border-collapse:collapse; text-align: center"| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 1px"|| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 0 0 0"|| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 0 0 0 1px"|| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>0</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px;border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>a</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #FFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>|-| style="background-color: #FFEECC; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px"|<tex>b</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>0</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>1</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>2</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>3</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>| style="background-color: #E0FFFF; width: 40px; height: 40px; border-color: #aaa; border-style: solid; border-width: 1px 1px 1px 1px" |<tex>4</tex>|}
== Время работы Источники информации ==* http://pages.cpsc.ucalgary.ca/~pmohasse/private-lcs.pdf