Алгоритм Мейна-Лоренца — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = '''Повтором''' (англ. ''repeatition'') называется непустая строка вида <math>\alpha...»)
 
Строка 30: Строка 30:
 
{{Утверждение
 
{{Утверждение
 
|id=kindscount
 
|id=kindscount
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>, где <tex>i</tex> индекс конца повтора в строке <tex>v</tex>.
+
|statement=<math>2p -RS[p] \leqslant i \leqslant p - RP[p + 1]</math>, где <tex>i</tex> индекс конца повтора в строке <tex>v</tex>.
 
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
 
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
 
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).
 
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).
Строка 40: Строка 40:
 
# <tex> k = u[(u.len - b + 1) .. u.len] = m = v[(i - p + 1) .. p] </tex>  
 
# <tex> k = u[(u.len - b + 1) .. u.len] = m = v[(i - p + 1) .. p] </tex>  
 
# <tex> l = v[1 .. (i - p)] = n = v[(p + 1) .. i] </tex>
 
# <tex> l = v[1 .. (i - p)] = n = v[(p + 1) .. i] </tex>
<tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>v[1 .. p]</tex> имеют общий суффикс длины не менее <tex>b</tex>: <tex>2p - i = b \leq RS[p]</tex>. <br>
+
<tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>v[1 .. p]</tex> имеют общий суффикс длины не менее <tex>b</tex>: <tex>2p - i = b \leqslant RS[p]</tex>. <br>
<tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> v[p+1..v.len]</tex> имеют общий префикс длины не менее <tex>p-b = i-p</tex>: <tex>i - p \leq RP[p + 1] </tex>
+
<tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> v[p+1..v.len]</tex> имеют общий префикс длины не менее <tex>p-b = i-p</tex>: <tex>i - p \leqslant RP[p + 1] </tex>
 
}}
 
}}
  
Строка 58: Строка 58:
 
{{Утверждение
 
{{Утверждение
 
|id=kindscount
 
|id=kindscount
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
+
|statement=<math> p - LS[u.len - p] \leqslant i \leqslant LP[u.len - p + 1] </math>
 
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
 
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
 
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).
 
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).
Строка 68: Строка 68:
 
# <tex> k = u[(u.len - b + 1) .. (u.len - p)] = m = u[(u.len - b + p + 1)  .. u.len] </tex>  
 
# <tex> k = u[(u.len - b + 1) .. (u.len - p)] = m = u[(u.len - b + p + 1)  .. u.len] </tex>  
 
# <tex> l = u[(u.len - p + 1) .... (u.len - b + p)] = n = v[1 .... i] </tex>
 
# <tex> l = u[(u.len - p + 1) .... (u.len - b + p)] = n = v[1 .... i] </tex>
<tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>u[(u.len - b + 1) .. u.len]</tex> имеют общий префикс длины не менее <tex>b - p = p - i</tex>: <tex> p - i \leq LS[u.len - p]</tex>. <br>
+
<tex>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>u[(u.len - b + 1) .. u.len]</tex> имеют общий префикс длины не менее <tex>b - p = p - i</tex>: <tex> p - i \leqslant LS[u.len - p]</tex>. <br>
<tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> u[(u.len - p)..u.len]</tex> имеют общий суффикс длины не менее <tex>i</tex>: <tex>i \leq LP[u.len - p + 1] </tex>
+
<tex>(2)</tex> эквивалентно тому, что строки <tex> v</tex> и <tex> u[(u.len - p)..u.len]</tex> имеют общий суффикс длины не менее <tex>i</tex>: <tex>i \leqslant LP[u.len - p + 1] </tex>
 
}}
 
}}
  

Версия 14:47, 30 апреля 2015

Определение:
Повтором (англ. repeatition) называется непустая строка вида [math]\alpha\alpha[/math]

Алгоритм Мейна-Лоренца (англ. Main-Lorentz algorithm) — алгоритм на строках, позволяющий найти все повторы в строке [math]s[1..n][/math] за [math]O(n \log n)[/math]

Алгоритм

Так как повторов строке [math] \Omega(n^2)[/math], мы не можем хранить их в явном виде. Будем хранить повторы блоками вида [math](length, first, last)[/math], где [math] length [/math] — это длина повтора, а [math] [first, last] [/math] — промежуток индексов, в которых заканчиваются повторы такой длины. Для каждой длины может быть несколько блоков.

Данный алгоритм — это алгоритм типа "разделяй и властвуй":

  1. Разделим строку пополам
  2. Заметим, что повторы делятся на две группы: пересекающие и не пересекающие границу раздела
  3. Рекурсивно запустимся от каждой половинки — так мы найдем повторы, которые не пересекают границу раздела
  4. Далее рассмотрим процесс нахождения повторов, которые пересекают границу раздела

Повторы, пересекающие границу раздела, можно разделить на две группы по положению центра повтора: правые и левые.

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

Рассмотрим строку [math]t = u + v[/math], пусть [math]shift[/math] — индекс начала [math]t[/math] в исходной строке [math]s[/math]

  1. Предподсчитаем следующие массивы c помощью Z-функции:
    1. [math] RP[i] = lcp(v[i..v.len], v) [/math], то есть наибольший общий префикс строк v[i..v.len] и v
    2. [math] RS[i] = lcs(v[1..i], u) [/math], то есть наибольший общий суффикс строк v[1..i] и u
  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] \leqslant i \leqslant p - RP[p + 1][/math], где [math]i[/math] индекс конца повтора в строке [math]v[/math].
[math]\triangleright[/math]

Рассмотрим правый повтор [math]ww[/math].
Обозначим как [math]k[/math] ту часть первой полвины повтора, которая принадлежит [math]u[/math], а как [math]l[/math] — ту часть первого половины, которая принадлежит [math]v[/math]. Равные им подстроки во первой половине обозначим как [math]m[/math] и [math]n[/math](см. рисунок).

RightRepetition.png
Пусть [math] b [/math] — длина [math]k[/math].
Заметим, что [math]w = k + l = m + n[/math] и [math] k = m, l = n [/math].
Тогда

  1. [math] k = u[(u.len - b + 1) .. u.len] = m = v[(i - p + 1) .. p] [/math]
  2. [math] l = v[1 .. (i - p)] = n = v[(p + 1) .. i] [/math]

[math](1)[/math] эквивалентно тому, что [math]u[/math] и [math]v[1 .. p][/math] имеют общий суффикс длины не менее [math]b[/math]: [math]2p - i = b \leqslant RS[p][/math].

[math](2)[/math] эквивалентно тому, что строки [math] v[/math] и [math] v[p+1..v.len][/math] имеют общий префикс длины не менее [math]p-b = i-p[/math]: [math]i - p \leqslant RP[p + 1] [/math]
[math]\triangleleft[/math]

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

Рассмотрим строку [math]t = u + v[/math], пусть [math]shift[/math] — индекс начала [math]t[/math] в исходной строке [math]s[/math]

  1. Предподсчитаем следующие массивы с помощью Z-функции:
    1. [math] LP[i] = lcp(u[i..u.len], v) [/math], то есть наибольший общий префикс строк u[i..u.len] и v
    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] \leqslant i \leqslant LP[u.len - p + 1] [/math]
[math]\triangleright[/math]

Рассмотрим правый повтор [math]ww[/math].
Обозначим как [math]m[/math] ту часть первой второй повтора, которая принадлежит [math]u[/math], а как [math]n[/math] — ту часть второго половины, которая принадлежит [math]v[/math]. Равные им подстроки во второй половине обозначим как [math]k[/math] и [math]l[/math](см. рисунок).

LeftRepetition.png
Пусть [math] b [/math] — длина [math]k+l+m[/math]. Заметим, что [math]w = k + l = m + n[/math] и [math] k = m, l = n [/math].
Тогда

  1. [math] k = u[(u.len - b + 1) .. (u.len - p)] = m = u[(u.len - b + p + 1) .. u.len] [/math]
  2. [math] l = u[(u.len - p + 1) .... (u.len - b + p)] = n = v[1 .... i] [/math]

[math](1)[/math] эквивалентно тому, что [math]u[/math] и [math]u[(u.len - b + 1) .. u.len][/math] имеют общий префикс длины не менее [math]b - p = p - i[/math]: [math] p - i \leqslant LS[u.len - p][/math].

[math](2)[/math] эквивалентно тому, что строки [math] v[/math] и [math] u[(u.len - p)..u.len][/math] имеют общий суффикс длины не менее [math]i[/math]: [math]i \leqslant LP[u.len - p + 1] [/math]
[math]\triangleleft[/math]

Асимптотика

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

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

Источники

  • 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