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

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

Версия 23:59, 26 апреля 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]

  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] [x, y] [/math]:

Утверждение:
[math]2p -RS[p] \leq i \leq p - RP[p + 1][/math]
[math]\triangleright[/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] [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]

Результат

  1. Рекурсивно найдем повторы, полностью лежащие в одной из половинок
  2. Вычислим LP, LS, RP, RS для t с помощью z-функции: [math] O(n) [/math]
  3. Найдем правые и левые повторы, как изложено выше: [math] O(n) [/math]

Асимптотика

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

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