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