102
правки
Изменения
Нет описания правки
=== Нахождение правых повтров ===
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>sshift</tex> {{---}} индекс начала <tex>shiftt</tex> [[Файл:RightRepetition.png|600px]]в исходной строке <tex>s<br/tex>
# Предподсчитаем следующие массивы c помощью z-функции:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, где <tex> lcp </tex> {{---}} то есть наибольший общий префиксстрок v[i..v.len] и v## <tex> RS[i] = lcs(v[1..i], u) </tex>, где <tex> lcs </tex> {{---}} то есть наибольший общий суффиксстрок v[1..i] и u# Переберем длину повтора <tex> 2p </tex>и будем искать все повторы такой длины. Для этого для каждого <tex> p </tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex>(позднее покажем, как это сделать).
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex>
|proof= Рассмотрим правый повтор <tex>ww</tex>.
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>, то есть той части повтора, которая принадлежит <tex>u</tex>.
[[Файл:RightRepetition.png|600px]]<br>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
=== Нахождение левых повтров ===
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>sshift</tex> {{---}} индекс начала <tex>shiftt</tex> [[Файл:LeftRepetition.png|600px]]в исходной строке <tex>s<br/tex>
# Предподсчитаем следующие массивы с помощью z-функции:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, где <tex> lcp </tex> {{---}} то есть наибольший общий префиксстрок u[i..u.len] и v
## <tex> LS[i] = lcs(u[1..i], u) </tex>, где <tex> lcs </tex> {{---}} наибольший общий суффикс
# Переберем длину повтора <tex> 2p </tex>и будем искать все повторы такой длины. Для этого для каждого <tex> p </tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex>(позднее покажем, как это сделать).
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex>
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
|proof= Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>, то есть той части повтора, которая принадлежит <tex>u</tex>.
[[Файл:LeftRepetition.png|600px]]<br>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
