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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
  
 
# Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
 
# Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк v[i..v.len] и v
+
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк <tex> v[i..v.len] </tex> и <tex> v </tex>
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк v[1..i] и u
+
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк <tex> v[1..i]</tex> и <tex> u </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 + u.len, y + shift + u.len) </tex>
 
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex>
Строка 39: Строка 39:
  
 
# Предподсчитаем следующие массивы с помощью [[Z-функция | Z-функции]]:
 
# Предподсчитаем следующие массивы с помощью [[Z-функция | Z-функции]]:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк u[i..u.len] и v
+
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк <tex> u[i..u.len] </tex> и <tex> v </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> u[1 ..i] </tex> и <tex> u </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 + u.len, y + shift + u.len) </tex>
 
# Добавим к ответу, учитывая смещение в исходной строке <tex> s </tex> : <tex>(2p, x + shift + u.len, y + shift + u.len) </tex>

Версия 16:35, 30 апреля 2015

Алгоритм Мейна-Лоренца (англ. 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] — промежуток индексов, в каждом из которых заканчивается повтор такой длины. Для каждой длины может быть несколько блоков.

Данный алгоритм — это алгоритм типа "разделяй и властвуй": разделим строку пополам, рекурсивно запустимся от каждой половинки — так мы найдем повторы, которые не пересекают границу раздела. Далее рассмотрим процесс нахождения повторов, которые пересекают границу раздела. Их можно разделить на две группы по положению центра повтора: правые и левые.

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

Рассмотрим строку [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], то есть наибольший общий префикс строк [math] v[i..v.len] [/math] и [math] v [/math]
    2. [math] RS[i] = lcs(v[1..i], u) [/math], то есть наибольший общий суффикс строк [math] v[1..i][/math] и [math] u [/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] \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], то есть наибольший общий префикс строк [math] u[i..u.len] [/math] и [math] v [/math]
    2. [math] LS[i] = lcs(u[1..i], u) [/math], где [math] lcs [/math] — наибольший общий суффикс строк [math] u[1 ..i] [/math] и [math] u [/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