Изменения

Так как повторов строке <tex> \Omega(n^2)</tex>, мы не можем хранить их в явном виде. Будем хранить повторы блоками вида <tex>(length, first, last)</tex>, где <tex> length </tex> {{---}} это длина повтора, а <tex> [first, last] </tex> {{---}} промежуток индексов, в каждом из которых заканчиваются повторы заканчивается повтор такой длины. Для каждой длины может быть несколько блоков.

Данный алгоритм {{---}} это алгоритм типа "разделяй и властвуй":# Разделим разделим строку пополам# Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела# Рекурсивно рекурсивно запустимся от каждой половинки {{---}} так мы найдем повторы, которые не пересекают границу раздела# . Далее рассмотрим процесс нахождения повторов, которые пересекают границу раздела Повторы, пересекающие границу раздела, . Их можно разделить на две группы по положению центра повтора: правые и левые.