102
правки
Изменения
Нет описания правки
# Предподсчитаем следующие массивы с помощью z-функции:
## <tex> LP[i] = lcp(u[i..u.len], uv) </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>.
