102
правки
Изменения
Нет описания правки
'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[#repeation | повторы]] в строке <tex>s[1..\dotsc n]</tex> за <tex>O(n \log n)</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> RS[i] = lcs(v[1..\dotsc i], u) </tex>, то есть наибольший общий суффикс строк <tex> v[1..\dotsc 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>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <tex> k = u[(u.len - b + 1) .. \dotsc u.len] = m = v[(i - p + 1) .. \dotsc p] </tex> # <tex> l = v[1 .. \dotsc (i - p)] = n = v[(p + 1) .. \dotsc i] </tex><tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>v[1 .. \dotsc p]</tex> имеют общий суффикс длины не менее <tex>b</tex>: <tex>2p - i = b \leqslant RS[p]</tex>. <br><tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> v[p+1..\dotsc v.len]</tex> имеют общий префикс длины не менее <tex>p-b = i-p</tex>: <tex>i - p \leqslant RP[p + 1] </tex>
}}
# Предподсчитаем следующие массивы с помощью [[Z-функция | Z-функции]]:
## <tex> LP[i] = lcp(u[i..\dotsc u.len], v) </tex>, то есть наибольший общий префикс строк <tex> u[i..\dotsc u.len] </tex> и <tex> v </tex>## <tex> LS[i] = lcs(u[1..\dotsc i], u) </tex>, где <tex> lcs </tex> {{---}} наибольший общий суффикс строк <tex> u[1 ..\dotsc 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>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <tex> k = u[(u.len - b + 1) .. \dotsc (u.len - p)] = m = u[(u.len - b + p + 1) \dotsc .. u.len] </tex> # <tex> l = u[(u.len - p + 1) .... \dotsc (u.len - b + p)] = n = v[1 ... \dotsc . i] </tex><tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>u[(u.len - b + 1) .. \dotsc u.len]</tex> имеют общий префикс длины не менее <tex>b - p = p - i</tex>: <tex> p - i \leqslant LS[u.len - p]</tex>. <br><tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> u[(u.len - p)..\dotsc u.len]</tex> имеют общий суффикс длины не менее <tex>i</tex>: <tex>i \leqslant LP[u.len - p + 1] </tex>
}}
== Асимптотика ==
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
