Участница:Mariashka

Определение:

Повтором (англ. repeatition) называется непустая строка вида [math]\alpha\alpha[/math]

Алгоритм Мейна-Лоренца (англ. Main-Lorentz algorithm) — алгоритм на строках, позволяющий найти все повторы в строке [math]s[1..n][/math] за [math]O(n \log n)[/math]

Алгоритм

Данный алгоритм — это алгоритм "разделяй и властвуй":

1. Разделим строку пополам
2. Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
3. Рекурсивно запустимся от каждой половинки — так мы найдем повторы, которые не пересекают границу раздела
4. Нахождение повторов, которые пересекают границу раздела

Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора.

Так как повторов строке [math] \Omega(n^2)[/math], мы не можем хранить их в явном виде. Будем хранить повторы блоками вида [math](length, first, last)[/math], где [math] length [/math] — это длина повтора, а [math] [first, last] [/math] — промежуток индексов, в которых заканчиваются повторы такой длины.

Нахождение правых повтров

Рассмотрим строку [math]t = uv[/math], пусть начало [math]t[/math] в исходной строке [math]s[/math] — [math]shift[/math]

1. Предподсчитаем следующие массивы:
   1. [math] RP[i] = lcp(v[i..v.len], v) [/math], где [math] lcp [/math] — наибольший общий префикс
   2. [math] RS[i] = lcs(v[1..i], u) [/math], где [math] lcs [/math] — наибольший общий суффикс
2. Переберем длину повтора [math] 2p [/math]. Для каждого [math] p [/math] получим интервал индексов конца повтора в строке [math] v [/math]: [math] [x, y] [/math].
3. Добавим к ответу, учитывая смещение в исходной строке [math] s [/math] : [math](2p, x + shift + u.len, y + shift + u.len) [/math]

Итоговая асимптотика: [math] O(t) [/math]

Докажем следующее утверждение для нахождения интервала [math] [x, y] [/math]:

Утверждение:

[math]2p -RS[p] \leq i \leq p - RP[p + 1][/math]

[math]\triangleright[/math]

Пусть i - индекс конца повтора в строке v, тогда b = 2p - i - длина части повтора принадлежащей u. Пусть наш повтор [math]\alpha\alpha[/math], тогда [math]\alpha = u[(u.len - b + 1) .. (u.len)] + v[1 .. (i - p)] = v[(i - p + 1) .. i] [/math] TODO

[math]\triangleleft[/math]

Нахождение левых повтров

Рассмотрим строку [math]t = uv[/math], пусть начало [math]t[/math] в исходной строке [math]s[/math] — [math]shift[/math]

1. Предподсчитаем следующие массивы:
   1. [math] LP[i] = lcp(u[i..u.len], u) [/math], где [math] lcp [/math] — наибольший общий префикс
   2. [math] LS[i] = lcs(u[1..i], u) [/math], где [math] lcs [/math] — наибольший общий суффикс
2. Переберем длину повтора [math] 2p [/math]. Для каждого [math] p [/math] получим интервал индексов конца повтора в строке [math] v [/math]: [math] [x, y] [/math].
3. Добавим к ответу, учитывая смещение в исходной строке [math] s [/math] : [math](2p, x + shift + u.len, y + shift + u.len) [/math]

Итоговая асимптотика: [math] O(t) [/math]

Докажем следующее утверждение для нахождения интервала [math] [x, y] [/math]:

Утверждение:

[math] p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] [/math]

[math]\triangleright[/math]

TODO

[math]\triangleleft[/math]

Асимптотика

Ассимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, [math] O(n \log n) [/math].

Количество блоков в ответе также будет [math] O(n \log n) [/math], так как при каждом рекрсивном запуске добавляется [math] O(1) [/math] блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.