Изменения

Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).

Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>

Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>

Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).

Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.

Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>

Количество блоков в ответе также будет <tex> O(n \log n) </tex>: при каждом рекурсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение <tex>M(n)=2M(n/2)+O(n)</tex>.

== Источники информации ==

* ''Main, M., Lorentz, R.J.'' — '''An O(n log n) Algorithm for Finding All Repetitions in a String'''. 1982

* ''Билл Смит'' — '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Основные определения. Простые комбинаторные свойства слов]]