1632
правки
Изменения
м
Рассмотрим строку Левые повторы находим аналогично правым, кроме вычисления интервала <tex>t</tex>[x, пусть <tex>shifty] </tex> {{---}} индекс начала для заданного <tex>t</tex> в исходной строке <tex>s</tex>.<br># Разобьем ее на две строки <tex> u p</tex> и <tex> v </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 \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> Итоговая асимптотика: <tex> O(t) </tex>
rollbackEdits.php mass rollback
'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repeation repetition | тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>
== Алгоритм ==
Так как повторов строке <tex> O(n^2)</tex>, мы не можем хранить их в явном виде. Будем хранить повторы несколько подряд идущих (по индексу конца) повторов одной длины блоками вида <tex>(length, first, last)</tex>, где <tex> length </tex> {{---}} это длина повтора, а <tex> [first, last] </tex> {{---}} промежуток индексов, в каждом из которых заканчивается повтор такой длины. Для каждой длины может быть несколько блоков.
Данный алгоритм {{---}} это алгоритм типа "разделяй и властвуй": разделим строку пополам, рекурсивно запустимся от каждой половинки {{---}} так мы найдем повторы, которые не пересекают границу раздела. Далее рассмотрим процесс нахождения повторов, которые пересекают границу раздела. Их можно разделить на две группы по положению центра повтора: правые и левые.
# Разобьем ее на две строки <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>
{{Утверждение
|id=kindscount
|statement=<math>2p -RS[p] \leqslant i \leqslant p - RP[p + 1]</math>, где <tex>i</tex> {{---}} индекс конца повтора длины <tex>2p</tex> в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).
<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex> :</i><br>
[[Файл:RightRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
=== Нахождение левых повтров ===
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
{{Утверждение
|id=kindscount
|statement=<math> p - LS[u.len - p] \leqslant i \leqslant LP[u.len - p + 1] </math>, где <tex>i</tex> {{---}} индекс конца повтора длины <tex>2p</tex> в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).
<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex>:</i><br>
[[Файл:LeftRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Асимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <tex> O(n \log n) </tex> из рекурентного соотношения <tex>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [[Сортировка слиянием | сортировки слиянием]]).
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при : на каждом рекрсивном рекурсивном запуске при рассмотрении повторов, которые пересекают границу раздела, добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а (их количество линейно относительно длины строки. == Источники информации ==* ''Main), из чего получаем аналогичное рекурентное соотношение <tex>M., Lorentz, R.J.'' — '''An (n)=2M(n/2)+O(n log n) Algorithm for Finding All Repetitions in a String'''. 1982* ''Билл Смит'' — '''Методы и алгоритмы вычислений на строках'''</tex>. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
== См. также ==
* [[Алгоритм Ландау-Шмидта]]
* [[Алгоритм Крочемора]]
== Источники информации ==
* ''Main, M., Lorentz, R.J.'' — '''An O(n log n) Algorithm for Finding All Repetitions in a String'''. 1982
* ''Билл Смит'' — '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
* [http://e-maxx.ru/algo/string_tandems MAXimal :: algo :: Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения. Простые комбинаторные свойства слов]]
