102
правки
Изменения
Новая страница: «{{Определение |definition = '''Повтором''' (англ. ''repeatition'') называется непустая строка вида <math>\alpha...»
{{Определение
|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 = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы c помощью [http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функции]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк v[i..v.len] и v
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк v[1..i] и u
# Переберем длину повтора <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>, где <tex>i</tex> индекс конца повтора в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).
[[Файл:RightRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <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>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>v[1 .. p]</tex> имеют общий суффикс длины не менее <tex>b</tex>: <tex>2p - i = b \leq 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>t = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы с помощью [http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функции]:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк u[i..u.len] и v
## <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= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).
[[Файл:LeftRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <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>(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>(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> O(n \log n) </tex> из рекурентного соотношения <tex>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.92.D1.80.D0.B5.D0.BC.D1.8F_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D1.8B сортировки слиянием]).
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
== Источники ==
* ''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
|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 = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы c помощью [http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функции]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк v[i..v.len] и v
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк v[1..i] и u
# Переберем длину повтора <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>, где <tex>i</tex> индекс конца повтора в строке <tex>v</tex>.
|proof= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex>(см. рисунок).
[[Файл:RightRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <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>(1)</tex> эквивалентно тому, что <tex>u</tex> и <tex>v[1 .. p]</tex> имеют общий суффикс длины не менее <tex>b</tex>: <tex>2p - i = b \leq 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>t = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>
# Предподсчитаем следующие массивы с помощью [http://neerc.ifmo.ru/wiki/index.php?title=Z-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F Z-функции]:
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк u[i..u.len] и v
## <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= Рассмотрим правый повтор <tex>ww</tex>.<br>
Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex>(см. рисунок).
[[Файл:LeftRepetition.png|600px]]<br>
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </tex>. <br>
Тогда
# <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>(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>(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> O(n \log n) </tex> из рекурентного соотношения <tex>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC#.D0.92.D1.80.D0.B5.D0.BC.D1.8F_.D1.80.D0.B0.D0.B1.D0.BE.D1.82.D1.8B сортировки слиянием]).
Количество блоков в ответе также будет <tex> O(n \log n) </tex>, так как при каждом рекрсивном запуске добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора, а их количество линейно относительно длины строки.
== Источники ==
* ''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
