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