102
правки
Изменения
Нет описания правки
# Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк <tex> v[i..v.len] </tex> и <tex> v</tex>## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк <tex> v[1..i] </tex> и <tex> u</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>
# Предподсчитаем следующие массивы с помощью [[Z-функция | Z-функции]]:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк <tex> u[i..u.len] </tex> и <tex> v</tex>## <tex> LS[i] = lcs(u[1..i], u) </tex>, где <tex> lcs </tex> {{---}} наибольший общий суффиксстрок <tex> u[1 ..i] </tex> и <tex> u </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>
