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