Изменения

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

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