=== Нахождение левых повтров ===
Рассмотрим строку Левые повторы находим аналогично правым, кроме вычисления интервала <tex>t</tex>[x, пусть <tex>shifty] </tex> {{---}} индекс начала для заданного <tex>t</tex> в исходной строке <tex>s</tex>.<br># Разобьем ее на две строки <tex> u p</tex> и <tex> v </tex>, как следствие, предподсчета.# Предподсчитаем следующие массивы с помощью [[Z-функция | Z-функции]]массивы:## <tex> LP[i] = lcp(u[i \dotsc u.len], \, v) </tex>, то есть наибольший общий префикс строк <tex> u[i \dotsc u.len] </tex> и <tex> v </tex>## <tex> LS[i] = lcs(u[1 \dotsc i], \, u) </tex>, где <tex> lcs </tex> {{---}} то есть наибольший общий суффикс строк <tex> u[1 \dotsc i] </tex> и <tex> u </tex># Переберем длину повтора <tex> 2p </tex> и будем искать все повторы такой длины: для каждого <tex> p \in [1, \, t.len /2]</tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex> (по формуле, которую докажем позднее). Добавим полученный интервал к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex> Итоговая асимптотика: <tex> O(t) </tex>
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
