Участница:Mariashka — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
 
(не показано 12 промежуточных версий этого же участника)
Строка 1: Строка 1:
{{Определение
 
|definition =
 
'''Повтором''' (англ. ''repeatition'') называется непустая строка вида <math>\alpha\alpha</math>
 
}}
 
'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все повторы в строке <tex>s[1..n]</tex> за <tex>O(n \log n)</tex>
 
  
== Алгоритм ==
 
Данный алгоритм {{---}} это алгоритм "разделяй и властвуй":
 
# Разделим строку пополам
 
# Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
 
# Рекурсивно запустимся от каждой половинки {{---}} так мы найдем повторы, которые не пересекают границу раздела
 
# Нахождение повторов, которые пересекают границу раздела
 
 
Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора.
 
 
Так как повторов строке <tex> \Omega(n^2)</tex>, мы не можем хранить их в явном виде. Будем хранить повторы блоками вида <tex>(length, first, last)</tex>, где <tex> length </tex> {{---}} это длина повтора, а <tex> [first, last] </tex> {{---}} промежуток индексов, в которых заканчиваются повторы такой длины.
 
 
=== Нахождение правых повтров ===
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 
 
# Предподсчитаем следующие массивы:
 
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, где <tex> lcp </tex> {{---}} наибольший общий префикс
 
## <tex> RS[i] = lcs(v[1..i], u) </tex>, где <tex> lcs </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> O(t) </tex>
 
 
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
 
{{Утверждение
 
|id=kindscount
 
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>
 
|proof= Пусть 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
 
}}
 
 
=== Нахождение левых повтров ===
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 
 
# Предподсчитаем следующие массивы:
 
## <tex> LP[i] = lcp(u[i..u.len], u) </tex>, где <tex> lcp </tex> {{---}} наибольший общий префикс
 
## <tex> LS[i] = lcs(u[1..i], u) </tex>, где <tex> lcs </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> O(t) </tex>
 
 
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
 
{{Утверждение
 
|id=kindscount
 
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
 
|proof= TODO
 
}}
 
 
== Асимптотика ==
 
Ассимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <tex> O(n \log n) </tex>.
 
 
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
 

Текущая версия на 14:38, 30 апреля 2015