Посчитаем эти квадраты для строк abbabb и bababb. Возьмём <tex> k = 3 </tex>. Тогда предподсчитанные квадраты, которые понадобятся для дальнейшего вычисления НОП, выглядят так:
[[Файл{||{|class="wikitable" style="background-color:4 russians lcs precalc.png]]#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>|}|}
=== Вычисление НОП на сжатой матрице ===
