102
правки
Изменения
Нет описания правки
Рассмотрим строку <tex>t = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы c помощью [http://neerc.ifmo.ru/wiki/index.php?title=[Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F функция | Z-функции]]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк v[i..v.len] и v
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк v[1..i] и u
Рассмотрим строку <tex>t = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы с помощью [http://neerc.ifmo.ru/wiki/index.php?title=[Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F функция | Z-функции]]:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк u[i..u.len] и v
## <tex> LS[i] = lcs(u[1..i], u) </tex>, где <tex> lcs </tex> {{---}} наибольший общий суффикс
== Асимптотика ==
Ассимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <tex> O(n \log n) </tex> из рекурентного соотношения <tex>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.92.D1.80.D0.B5.D0.BC.D1.8F_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D1.8B [Сортировка слиянием | сортировки слиянием]]).
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
