Участница: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]s = uv[/math]. Переберем длину повтора [math] 2p [/math]. Для каждого [math] p [/math] получим неравенство для [math] i [/math] - индекса конца повтора в строке [math] v [/math]. Так как мы рассматриваем повторы, пересекающие границу, повтор всегда оканчивается в [math] v [/math]. Для этого предподсчитаем следующие массивы:

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] - наибольший общий суффикс

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

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

[math]\triangleright[/math]

TODO

[math]\triangleleft[/math]

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

Рассмотрим строку [math]s = uv[/math]. Переберем длину повтора [math] 2p [/math]. Для каждого [math] p [/math] получим неравенство для [math] i [/math] - индекса конца повтора в строке [math] v [/math]. Для этого предподсчитаем следующие массивы:

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] - наибольший общий суффикс

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

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

[math]\triangleright[/math]

TODO

[math]\triangleleft[/math]