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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = '''Повтором''' (англ. ''repeatition'') называется непустая строка вида <math>\alpha...»)
 
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 2 участников)
Строка 1: Строка 1:
{{Определение
+
 
|definition =
+
'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repetition | тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>
'''Повтором''' (англ. ''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> O(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>  
+
Рассмотрим строку <tex>t</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>.<br>
 
+
# Разобьем ее на две строки <tex> u </tex> и <tex> v </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-функции]:
+
# Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
## <tex> RP[i] = lcp(v[i..v.len], v) </tex>, то есть наибольший общий префикс строк v[i..v.len] и v
+
#* <tex> RP[i] = lcp(v[i \dotsc v.len], \, v) </tex>, то есть наибольший общий префикс строк <tex> v[i \dotsc v.len] </tex> и <tex> v </tex>. Нахождение <tex>lcp(a,\,b[i \dotsc b.len])</tex> можно осуществить следующим образом: вычислим для строки <math> a+'\#'+b </math> [[Z-функция | Z-функцию]]. Очевидно, что в таком случае массивом <tex>lcp</tex> будет массив значений Z-функции, начиная с индекса <tex> a.len + 2 </tex>.
## <tex> RS[i] = lcs(v[1..i], u) </tex>, то есть наибольший общий суффикс строк v[1..i] и u
+
#* <tex> RS[i] = lcs(v[1 \dotsc i], \, u) </tex>, то есть наибольший общий суффикс строк <tex> v[1 \dotsc i]</tex> и <tex> u </tex>. Нахождение <tex>lcs(a,\,b[1 \dotsc i)</tex> можно осуществить следующим образом: вычислим для строки <math> reverse(a)+'\#'+reverse(b) </math> [[Z-функция | Z-функцию]]. Очевидно, что в таком случае массивом <tex>lcs</tex> будет перевернутый массив значений Z-функции, начиная с индекса <tex> a.len + 2 </tex>.
# Переберем длину повтора <tex> 2p </tex> и будем искать все повторы такой длины. Для этого для каждого <tex> p </tex> получим интервал индексов конца повтора в строке <tex> v </tex>: <tex> [x, y] </tex>(позднее покажем, как это сделать).
+
# Переберем длину повтора <tex> 2p </tex> и будем искать все повторы такой длины: для каждого <tex> p \in [1, \, t.len /2]</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>
 
  
 
Итоговая асимптотика: <tex> O(t) </tex>
 
Итоговая асимптотика: <tex> O(t) </tex>
Строка 30: Строка 20:
 
{{Утверждение
 
{{Утверждение
 
|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>2p</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> (см. рисунок).
  
 +
<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex> :</i><br>
 
[[Файл:RightRepetition.png|600px]]<br>
 
[[Файл:RightRepetition.png|600px]]<br>
 
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
 
Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
 
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </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> k = u[(u.len - b + 1) \dotsc u.len] = m = v[(i - p + 1) \dotsc  p] </tex>  
# <tex> l = v[1 .. (i - p)] = n = v[(p + 1) .. i] </tex>
+
# <tex> l = v[1 \dotsc (i - p)] = n = v[(p + 1) \dotsc 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 \dotsc 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 \dotsc v.len]</tex> имеют общий префикс длины не менее <tex>p-b = i-p</tex>: <tex>i - p \leqslant RP[p + 1] </tex>
 
}}
 
}}
  
 
=== Нахождение левых повтров ===
 
=== Нахождение левых повтров ===
Рассмотрим строку <tex>t = u + v</tex>, пусть <tex>shift</tex> {{---}} индекс начала <tex>t</tex> в исходной строке <tex>s</tex>  
+
Левые повторы находим аналогично правым, кроме вычисления интервала <tex> [x, y] </tex> для заданного <tex> p</tex> и, как следствие, предподсчета.
 
+
Предподсчитаем с помощью [[Z-функция | Z-функции]] массивы:
# Предподсчитаем следующие массивы с помощью [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 \dotsc u.len], \, v) </tex>, то есть наибольший общий префикс строк <tex> u[i \dotsc u.len] </tex> и <tex> v </tex>
## <tex> LP[i] = lcp(u[i..u.len], v) </tex>, то есть наибольший общий префикс строк u[i..u.len] и v
+
* <tex> LS[i] = lcs(u[1 \dotsc i], \, u) </tex>, то есть наибольший общий суффикс строк <tex> u[1 \dotsc i] </tex> и <tex> u </tex>
## <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>:
 
Докажем следующее утверждение для нахождения интервала <tex> [x, y] </tex>:
 
{{Утверждение
 
{{Утверждение
 
|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>, где <tex>i</tex> {{---}} индекс конца повтора длины <tex>2p</tex> в строке <tex>v</tex>.
 
|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> (см. рисунок).
  
 +
<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex>:</i><br>
 
[[Файл:LeftRepetition.png|600px]]<br>
 
[[Файл:LeftRepetition.png|600px]]<br>
 +
 
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
 
Пусть <tex> b </tex> {{---}} длина <tex>k+l+m</tex>.
 
Заметим, что <tex>w = k + l = m + n</tex> и <tex> k = m, l = n </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 - p)] = m = u[(u.len - b + p + 1)  .. u.len] </tex>  
+
# <tex> k = u[(u.len - b + 1) \dotsc  (u.len - p)] = m = u[(u.len - b + p + 1)   \dotsc 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) \dotsc  (u.len - b + p)] = n = v[1 \dotsc . 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) \dotsc  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) \dotsc u.len]</tex> имеют общий суффикс длины не менее <tex>i</tex>: <tex>i \leqslant 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>T(n)=2T(n/2)+O(n)</tex> (аналогичное доказательство для [[Сортировка слиянием | сортировки слиянием]]).
 +
 
 +
Количество блоков в ответе также будет <tex> O(n \log n) </tex>: на каждом рекурсивном запуске при рассмотрении повторов, которые пересекают границу раздела, добавляется <tex> O(1) </tex> блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение <tex>M(n)=2M(n/2)+O(n)</tex>.
 +
 
 +
== См. также ==
  
Количество блоков в ответе также будет <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
 
* ''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
 
* ''Билл Смит'' — '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс",  2006. ISBN 5-8459-1081-1
 +
* [http://e-maxx.ru/algo/string_tandems MAXimal :: algo :: Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца]
 +
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Основные определения. Простые комбинаторные свойства слов]]

Текущая версия на 19:13, 4 сентября 2022

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

Алгоритм

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

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

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

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

  1. Разобьем ее на две строки [math] u [/math] и [math] v [/math].
  2. Предподсчитаем следующие массивы c помощью Z-функции:
    • [math] RP[i] = lcp(v[i \dotsc v.len], \, v) [/math], то есть наибольший общий префикс строк [math] v[i \dotsc v.len] [/math] и [math] v [/math]. Нахождение [math]lcp(a,\,b[i \dotsc b.len])[/math] можно осуществить следующим образом: вычислим для строки [math] a+'\#'+b [/math] Z-функцию. Очевидно, что в таком случае массивом [math]lcp[/math] будет массив значений Z-функции, начиная с индекса [math] a.len + 2 [/math].
    • [math] RS[i] = lcs(v[1 \dotsc i], \, u) [/math], то есть наибольший общий суффикс строк [math] v[1 \dotsc i][/math] и [math] u [/math]. Нахождение [math]lcs(a,\,b[1 \dotsc i)[/math] можно осуществить следующим образом: вычислим для строки [math] reverse(a)+'\#'+reverse(b) [/math] Z-функцию. Очевидно, что в таком случае массивом [math]lcs[/math] будет перевернутый массив значений Z-функции, начиная с индекса [math] a.len + 2 [/math].
  3. Переберем длину повтора [math] 2p [/math] и будем искать все повторы такой длины: для каждого [math] p \in [1, \, t.len /2][/math] получим интервал индексов конца повтора в строке [math] v [/math]: [math] [x, y] [/math] (по формуле, которую докажем позднее). Добавим полученный интервал к ответу, учитывая смещение в исходной строке [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]2p[/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] (см. рисунок).

Разбиение строки [math]t[/math], с индексацией [math]u[/math] и [math]v[/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) \dotsc u.len] = m = v[(i - p + 1) \dotsc p] [/math]
  2. [math] l = v[1 \dotsc (i - p)] = n = v[(p + 1) \dotsc i] [/math]

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

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

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

Левые повторы находим аналогично правым, кроме вычисления интервала [math] [x, y] [/math] для заданного [math] p[/math] и, как следствие, предподсчета. Предподсчитаем с помощью Z-функции массивы:

  • [math] LP[i] = lcp(u[i \dotsc u.len], \, v) [/math], то есть наибольший общий префикс строк [math] u[i \dotsc u.len] [/math] и [math] v [/math]
  • [math] LS[i] = lcs(u[1 \dotsc i], \, u) [/math], то есть наибольший общий суффикс строк [math] u[1 \dotsc i] [/math] и [math] u [/math]

Докажем следующее утверждение для нахождения интервала [math] [x, y] [/math]:

Утверждение:
[math] p - LS[u.len - p] \leqslant i \leqslant LP[u.len - p + 1] [/math], где [math]i[/math] — индекс конца повтора длины [math]2p[/math] в строке [math]v[/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] (см. рисунок).

Разбиение строки [math]t[/math], с индексацией [math]u[/math] и [math]v[/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) \dotsc (u.len - p)] = m = u[(u.len - b + p + 1) \dotsc u.len] [/math]
  2. [math] l = u[(u.len - p + 1) \dotsc (u.len - b + p)] = n = v[1 \dotsc . i] [/math]

[math](1)[/math] эквивалентно тому, что [math]u[/math] и [math]u[(u.len - b + 1) \dotsc 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) \dotsc 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] блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение [math]M(n)=2M(n/2)+O(n)[/math].

См. также

Источники информации