|
|
| (не показано 16 промежуточных версий этого же участника) |
| Строка 1: |
Строка 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>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
| |
| − | }}
| |
| − |
| |
| − | == Общий алгоритм ==
| |
