102
правки
Изменения
Нет описания правки
|id=kindscount
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>, где <tex>i</tex> индекс конца повтора в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>Пусть Обозначим как <tex> b k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} длина ту часть первого повтора, которая принадлежит <tex>v</tex>. Аналогичные во второй половине как <tex>km</tex>, то есть той части повтора, которая принадлежит и <tex>un</tex>(см. рисунок).
[[Файл:RightRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
|id=kindscount
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
|proof= Пусть Рассмотрим правый повтор <tex> b ww</tex>.<br>Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} длина ту часть второго повтора, которая принадлежит <tex>v</tex>. Аналогичные во второй половине как <tex>k+l+m</tex>, то есть той части повтора, которая принадлежит и <tex>ul</tex>(см. рисунок).
[[Файл:LeftRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
