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>s = uv</tex>.
Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим неравенство для <tex> i </tex> - индекса конца повтора в строке <tex> v </tex>. Так как мы рассматриваем повторы, пересекающие границу, повтор всегда оканчивается в <tex> v </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> - наибольший общий суффикс
{{Утверждение
|id=kindscount
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>
|proof= TODO
}}
=== Нахождение левых повтров ===
Рассмотрим строку <tex>s = uv</tex>.
Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим неравенство для <tex> i </tex> - индекса конца повтора в строке <tex> v </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> - наибольший общий суффикс
{{Утверждение
|id=kindscount
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
|proof= TODO
}}
== Общий алгоритм ==
|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>s = uv</tex>.
Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим неравенство для <tex> i </tex> - индекса конца повтора в строке <tex> v </tex>. Так как мы рассматриваем повторы, пересекающие границу, повтор всегда оканчивается в <tex> v </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> - наибольший общий суффикс
{{Утверждение
|id=kindscount
|statement=<math>2p -RS[p] \leq i \leq p - RP[p + 1]</math>
|proof= TODO
}}
=== Нахождение левых повтров ===
Рассмотрим строку <tex>s = uv</tex>.
Переберем длину повтора <tex> 2p </tex>. Для каждого <tex> p </tex> получим неравенство для <tex> i </tex> - индекса конца повтора в строке <tex> v </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> - наибольший общий суффикс
{{Утверждение
|id=kindscount
|statement=<math> p - LS[u.len - p] \leq i \leq LP[u.len - p + 1] </math>
|proof= TODO
}}
== Общий алгоритм ==
