102
правки
Изменения
Нет описания правки
|id=kindscount
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>
|proof= Пусть i - индекс конца повтора в строке v, тогда b = 2p - i - длина части повтора принадлежащей u.Пусть наш повтор <math>\alpha\alpha</math>, тогда <math>\alpha = u[(u.len - b + 1) .. (u.len)] + v[1 .. (i - p)] = v[(i - p + 1) .. i] </math> TODO
}}
=== Результат ===
# Делим строку пополам# Рекурсивно найдем повторы, полностью лежащие в одной из половинок запускаемся от полученных строк # Вычислим LP, LS, RP, RS для t с помощью z-функции: <tex> O(nt) </tex># Найдем правые и левые повторы, как изложено выше: <tex> O(nt) </tex>
== Асимптотика ==
