102
правки
Изменения
Нет описания правки
== Алгоритм ==
Данный алгоритм {{- --}} это алгоритм "разделяй и властвуй":
# Разделим строку пополам
# Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
# Рекурсивно запустимся от каждой половинки {{- --}} так мы найдем повторы, которые не пересекают границу раздела
# Нахождение повторов, которые пересекают границу раздела
Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора.
Так как повторов строке <tex> \Omega(n^2)</tex>, мы не можем хранить их в явном виде. Будем хранить повторы блоками вида <tex>(length, first, last)</tex>, где <tex> length </tex> {{- --}} это длина повтора, а <tex> [first, last] </tex> {{--- }} промежуток индексов, в которых заканчиваются повторы такой длины.
=== Нахождение правых повтров ===
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{- --}} <tex>shift</tex>
# Предподсчитаем следующие массивы:
## <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> {{--- }} наибольший общий суффикс
# Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex>.
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift+ u.len, y + shift+ u.len) </tex>
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
=== Нахождение левых повтров ===
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{- --}} <tex>shift</tex>
# Предподсчитаем следующие массивы:
## <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> {{--- }} наибольший общий суффикс
# Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex>.
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift+ u.len, y + shift+ u.len) </tex>
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
}}
== Общий алгоритм н=Результат === # Рекурсивно найдем повторы, полностью лежащие в одной из половинок # Вычислим LP, LS, RP, RS для t с помощью z-функции: <tex> O(n) </tex># Найдем правые и левые повторы, как изложено выше: <tex> O(n) </tex> == Асимптотика ==Ассимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <tex> O(n \log n) </tex>. Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
