102
правки
Изменения
Нет описания правки
# Разобьем ее на две строки <tex> u </tex> и <tex> v </tex>.
# Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
#* <tex> RP[i] = lcp(v[i \dotsc v.len], \, v) </tex>, то есть наибольший общий префикс строк <tex> v[i \dotsc v.len] </tex> и <tex> v </tex>. Нахождение <tex>lcp(a,\,b[i \dotsc b.len])</tex> можно осуществить следующим образом: вычислим для строки <math> a+'\#'+b </math> [[Z-функция | Z-функцию]]. Очевидно, что в таком случае массивом <tex>lcp</tex> будет массив значений Z-функции, начиная с индекса <tex> a.len + 2 </tex>.
#* <tex> RS[i] = lcs(v[1 \dotsc i], \, u) </tex>, то есть наибольший общий суффикс строк <tex> v[1 \dotsc i]</tex> и <tex> u </tex>. Нахождение <tex>lcs(a,\,b[1 \dotsc i)</tex> можно осуществить следующим образом: вычислим для строки <math> reverse(a)+'\#'+reverse(b) </math> [[Z-функция | Z-функцию]]. Очевидно, что в таком случае массивом <tex>lcs</tex> будет перевернутый массив значений Z-функции, начиная с индекса <tex> a.len + 2 </tex>.
# Переберем длину повтора <tex> 2p </tex> и будем искать все повторы такой длины: для каждого <tex> p \in [1, \, t.len /2]</tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex> (по формуле, которую докажем позднее). Добавим полученный интервал к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex>
