102
правки
Изменения
Нет описания правки
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </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
