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