Алгоритм Мейна-Лоренца - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:13:16Z

rollbackEdits.php mass rollback

94.16.121.91 в 05:57, 1 сентября 2022

2022-09-01T05:57:53Z

Mariashka в 18:34, 30 апреля 2015

2015-04-30T18:34:23Z

Mariashka в 18:33, 30 апреля 2015

2015-04-30T18:33:16Z

Mariashka в 18:30, 30 апреля 2015

2015-04-30T18:30:46Z

Mariashka в 18:26, 30 апреля 2015

2015-04-30T18:26:23Z

Mariashka в 18:25, 30 апреля 2015

2015-04-30T18:25:43Z

Mariashka в 18:23, 30 апреля 2015

2015-04-30T18:23:20Z

Mariashka в 16:49, 30 апреля 2015

2015-04-30T16:49:14Z

Mariashka в 16:47, 30 апреля 2015

2015-04-30T16:47:54Z

← Предыдущая		Версия 16:13, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
−

	'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repetition \| тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>		'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repetition \| тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>

← Предыдущая		Версия 05:57, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
		+

	'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repetition \| тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>		'''Алгоритм Мейна-Лоренца''' (англ. ''Main-Lorentz algorithm'') {{---}} алгоритм на строках, позволяющий найти все [[Основные_определения,_связанные_со_строками#repetition \| тандемные повторы]] в строке <tex>s[1 \dotsc n]</tex> за <tex>O(n \log n)</tex>

@@ Строка 20: / Строка 20: @@
 {{Утверждение
 |id=kindscount
-|statement=<math>2p -RS[p] \leqslant i \leqslant p - RP[p + 1]</math>, где <tex>i</tex> индекс конца повтора длины <tex>2p</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>
 Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex> (см. рисунок).
@@ Строка 44: / Строка 44: @@
 {{Утверждение
 |id=kindscount
-|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>.
+|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>
 Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex> (см. рисунок).

@@ Строка 20: / Строка 20: @@
 {{Утверждение
 |id=kindscount
-|statement=<math>2p -RS[p] \leqslant i \leqslant 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>
 Обозначим как <tex>k</tex> ту часть первой полвины повтора, которая принадлежит <tex>u</tex>, а как <tex>l</tex> {{---}} ту часть первого половины, которая принадлежит <tex>v</tex>. Равные им подстроки во первой половине обозначим как <tex>m</tex> и <tex>n</tex> (см. рисунок).
@@ Строка 44: / Строка 44: @@
 {{Утверждение
 |id=kindscount
-|statement=<math> p - LS[u.len - p] \leqslant i \leqslant 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>
 Обозначим как <tex>m</tex> ту часть первой второй повтора, которая принадлежит <tex>u</tex>, а как <tex>n</tex> {{---}} ту часть второго половины, которая принадлежит <tex>v</tex>. Равные им подстроки во второй половине обозначим как <tex>k</tex> и <tex>l</tex> (см. рисунок).

@@ Строка 22: / Строка 22: @@
 |statement=<math>2p -RS[p] \leqslant i \leqslant 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>(см. рисунок).
+Обозначим как <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>
@@ Строка 46: / Строка 46: @@
 |statement=<math> p - LS[u.len - p] \leqslant i \leqslant 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>(см. рисунок).
+Обозначим как <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>

@@ Строка 24: / Строка 24: @@
 Обозначим как <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>
+<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex> :</i><br>
 [[Файл:RightRepetition.png|600px]]<br>
 Пусть <tex> b </tex> {{---}} длина <tex>k</tex>.<br>
@@ Строка 48: / Строка 48: @@
 Обозначим как <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>
+<i>Разбиение строки <tex>t</tex>, с индексацией <tex>u</tex> и <tex>v</tex>:</i><br>
 [[Файл:LeftRepetition.png|600px]]<br>

@@ Строка 11: / Строка 11: @@
 # Разобьем ее на две строки <tex> u </tex> и <tex> v </tex>.
 # Предподсчитаем следующие массивы c помощью [[Z-функция | Z-функции]]:
-#* <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> 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 \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 \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>

@@ Строка 63: / Строка 63: @@
 Асимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <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> блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение <tex>M(n)=2M(n/2)+O(n)</tex>.
 == См. также ==

@@ Строка 63: / Строка 63: @@
 Асимптотика алгоритма "разделяй и властвуй", каждый рекурсивный запуск которого линеен относительно длины строки, <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> блоков для каждой рассмотренной длины повтора (их количество линейно относительно длины строки), из чего получаем аналогичное рекурентное соотношение <tex>M(n)=2M(n/2)+O(n)</tex>.
 == См. также ==
@@ Строка 74: / Строка 74: @@
 * ''Билл Смит'' — '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс",  2006. ISBN 5-8459-1081-1
 * [http://e-maxx.ru/algo/string_tandems MAXimal :: algo :: Поиск всех тандемных повторов в строке. Алгоритм Мейна-Лоренца]
 [[Категория: Алгоритмы и структуры данных]]
 [[Категория: Основные определения. Простые комбинаторные свойства слов]]