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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
 
# Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
 
# Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
 
# Рекурсивно запустимся от каждой половинки {{---}} так мы найдем повторы, которые не пересекают границу раздела
 
# Рекурсивно запустимся от каждой половинки {{---}} так мы найдем повторы, которые не пересекают границу раздела
# Нахождение повторов, которые пересекают границу раздела
+
# Далее рассмотрим процесс нахождения повторов, которые пересекают границу раздела
  
 
Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора.
 
Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора.
Строка 18: Строка 18:
 
=== Нахождение правых повтров ===
 
=== Нахождение правых повтров ===
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 +
 +
[[Файл:RightRepetition.png|600px]]<br>
  
 
# Предподсчитаем следующие массивы:
 
# Предподсчитаем следующие массивы:
Строка 40: Строка 42:
 
=== Нахождение левых повтров ===
 
=== Нахождение левых повтров ===
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 
Рассмотрим строку <tex>t = uv</tex>, пусть начало <tex>t</tex> в исходной строке <tex>s</tex> {{---}} <tex>shift</tex>
 +
 +
[[Файл:LeftRepetition.png|600px]]<br>
  
 
# Предподсчитаем следующие массивы:
 
# Предподсчитаем следующие массивы:

Версия 19:12, 27 апреля 2015

Определение:
Повтором (англ. 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]

RightRepetition.png

  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]

LeftRepetition.png

  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] блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.