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