102
правки
Изменения
Нет описания правки
{{Утверждение
|id=kindscount
|statement=<math>2p -RS[p] \leqslant i \leqslant p - RP[p + 1]</math>, где <tex>i</tex> {{---}} индекс конца повтора длины <tex>2p</tex> в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex> (см. рисунок).
{{Утверждение
|id=kindscount
|statement=<math> p - LS[u.len - p] \leqslant i \leqslant LP[u.len - p + 1] </math>, где <tex>i</tex> {{---}} индекс конца повтора длины <tex>2p</tex> в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex> (см. рисунок).