Декомпозиция Линдона - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:13:14Z

rollbackEdits.php mass rollback

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

2022-09-01T05:59:44Z

85.89.127.27: /* Основные определения */

2018-12-21T13:21:05Z

‎Основные определения

77.234.212.37: /* Существование и единственность */

2018-02-13T10:20:39Z

‎Существование и единственность

77.234.212.37: /* Существование и единственность */

2018-02-13T10:12:11Z

‎Существование и единственность

Penguinni: /* См. также */

2017-03-21T18:18:15Z

‎См. также

Penguinni в 18:05, 21 марта 2017

2017-03-21T18:05:49Z

Penguinni в 17:57, 21 марта 2017

2017-03-21T17:57:25Z

Внесённые изменения

Shersh: /* Существование и единственность */ исправлен мелкий баг

2015-04-23T20:19:16Z

‎Существование и единственность: исправлен мелкий баг

Xottab: /* Поиск лексикографически минимального суффикса строки */

2014-06-13T20:31:41Z

‎Поиск лексикографически минимального суффикса строки

← Предыдущая		Версия 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 Майкл Наки].
−	\|}
−
	Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.		Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.

← Предыдущая		Версия 05:59, 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 Майкл Наки].
		+	\|}
		+
	Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.		Декомпозиция Линдона была изобретена Роджером Линдоном (англ. ''Roger Lyndon'') в 1954 году. Она используется для нахождения лексикографически минимального и максимального суффиксов строки, а также лексикографически минимального циклического сдвига.

@@ Строка 5: / Строка 5: @@
 {{Определение
 |id=def1.
-|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего суффикса.
+|definition='''Простая строка''' {{---}} строка, которая лексикографически меньше любого своего собственного суффикса.
 }}

@@ Строка 27: / Строка 27: @@
 . <tex>s + t</tex> {{---}} простая
 |proof=
-. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow s + t < t</tex>
+. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, тогда:
 . Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:

@@ Строка 27: / Строка 27: @@
 . <tex>s + t</tex> {{---}} простая
 |proof=
-. Так как <tex>s < t</tex>, то <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow s + t < t</tex>
+. Так как <tex>s < t</tex>, то либо <tex>s</tex> является префиксом <tex>t</tex>, либо <tex>\exists i : s[i] < t[i]</tex> и <tex>s[j] = t[j]</tex>, <tex>j < i \Rightarrow s + t < t</tex>
 . Пусть <tex>u</tex> {{---}} суффикс строки <tex>s + t</tex>. Тогда рассмотрим 3 возможных случая:

@@ Строка 399: / Строка 399: @@
 ==См. также==
+* [[Алгоритм Крочемора]]
 ==Примечания==

@@ Строка 397: / Строка 397: @@
 |statement= Строка <tex>T</tex> длины <tex>n</tex> может храниться в структуре данных памяти <tex>\mathcal{O}(n)</tex>, которая позволяет вычислять максимальный суффикс любой подстроки <tex>T</tex> за <tex>\mathcal{O}(1)</tex> времени. Данную структуру данных можно построить за <tex>\mathcal{O}(n)</tex> времени.
 }}
 ==Примечания==

@@ Строка 33: / Строка 33: @@
 * <tex>|u| = |t| \Rightarrow u = t \Rightarrow u > s + t</tex> по пункту 1
 * <tex>|u| < |t| \Rightarrow u</tex> {{---}} суффикс <tex>t</tex>. Так как <tex>t</tex> {{---}} простая, и <tex>t < u </tex> по определению <tex> \Rightarrow s + t < t < u</tex>
-* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> меньше самой строки <tex> s </tex> в каком-то символе, значит, <tex> s + t < s'' + t</tex>
+* <tex>|u| > |t| \Rightarrow s = s' + s''</tex>, <tex>u = s'' + t</tex>. Так как <tex>s</tex> {{---}} простая, то её суффикс <tex> s'' </tex> больше самой строки <tex> s </tex> в каком-то символе, значит, <tex> s + t < s'' + t</tex>
 }}

@@ Строка 183: / Строка 183: @@
 Более того, <tex>p</tex> может быть найдено за константное время с использованием улучшенного суффиксного массива строки <tex>T</tex>.
-|proof=  По Лемме 0 минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leqslant\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..j]</tex> является минимальным суффиксом  <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется случай <tex>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.
+|proof=  По лемме 0 минимальный суффикс равен либо <tex>T[p..j]</tex>, либо его кратчайшему непустому бордеру. Более того, в последнем случае длина минимального суффикса равна не превышает <tex>\displaystyle \frac{1}{2}|T[p..j]|\leqslant\frac{1}{2}|T[i..j]|</tex>. С другой стороны, по второму свойству канонических подстрок, длина <tex>S_{j}^{\alpha(i,j)}</tex> равна как минимум <tex>\displaystyle \frac{1}{2}|T[i..j]|</tex>. Таким образом, во втором случае минимальный суффикс <tex>T[i..j]</tex> является минимальным суффиксом  <tex>S_{j}^{\alpha(i,j)}</tex>. Заметим, что для <tex>i=j</tex> значения <tex>\alpha(i,\ j)</tex> не определены, но тогда выполняется случай <tex>(a)</tex> из условия леммы. Чтобы доказать финальное выражение, вспомним, что нахождение минимального суффикса <tex>Suf [i,\ j]</tex> {{---}} одна из базовых операций, поддерживаемых улучшенным суфмассивом.
 }}
 Требуемая структура данных, помимо улучшенного суфмассива, должна, для каждого <tex>j=1,\ \ldots,\ n</tex> содержать битовый вектор <tex>B_{j}</tex> длиной <tex>\alpha(1,\ j)</tex>. Положим <tex>B_{j}[\ell]=1</tex> тогда и только тогда, когда минимальный суффикс <tex>S_{j}^{\ell}</tex> длиннее, чем <tex>|S_{j}^{\ell-1}|</tex>. Для <tex>\ell=1</tex> мы всегда считаем <tex>B_{j}[1]=1</tex>, поскольку <tex>S_{j}^{1}</tex> является минимальным суффиксом самого себя. Вспомним, что количество канонических подстрок для каждого <tex>j</tex> равна <tex>\mathcal{O}(\log n)</tex> , поэтому каждый <tex>B_{j}</tex> вмещается в константное количество машинных слов и структура данных занимает <tex>\mathcal{O}(n)</tex> памяти.
 ===Алгоритм запроса===
-Предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex> c <tex>\alpha(i,\ j)=\ell</tex>. Наш подход основан на Лемме 1. Если выполняется случай <tex>(a)</tex>, лемма позволяет нам вычислить ответ за <tex>\mathcal{O}(1)</tex>. В общем случае, мы найдём минимальный суффикс <tex>S_{j}^{\ell}</tex>, сравним его с <tex>T[p..j]</tex> и вернём меньший из них.
+Предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex> c <tex>\alpha(i,\ j)=\ell</tex>. Наш подход основан на лемме 1. Если выполняется случай <tex>(a)</tex>, лемма позволяет нам вычислить ответ за <tex>\mathcal{O}(1)</tex>. В общем случае, мы найдём минимальный суффикс <tex>S_{j}^{\ell}</tex>, сравним его с <tex>T[p..j]</tex> и вернём меньший из них.
-Мы используем Лемму 1 и битовый вектор <tex>B_{j}</tex> чтобы посчитать минимальный суффикс <tex>S_{j}^{\ell}</tex>. Назовём <tex>\ell'</tex>  наибольший индекс, не превышающий <tex>\ell</tex>, такой, что <tex>B_{j}[\ell']=1</tex>. Заметим, что такой индекс всегда существует  (поскольку<tex> B_{j}[1]=1</tex>) и может быть найден за константное время с использованием битовых операций. Для любого индекса <tex>\ell''\in\{\ell'+1,\ \ldots,\ \ell\}</tex> мы имеем <tex>B_{j}[\ell'']=0</tex>, т.е., случай <tex>(b)</tex> Леммы 1 выполняется для <tex>S_{j}^{\ell''}</tex>. Тогда, по индукции, минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>. С другой стороны, <tex>B_{j}[\ell']=1</tex>, поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс <tex>S_{j}^{\ell}</tex> за константное время.
+Мы используем лемму 1 и битовый вектор <tex>B_{j}</tex> чтобы посчитать минимальный суффикс <tex>S_{j}^{\ell}</tex>. Назовём <tex>\ell'</tex>  наибольший индекс, не превышающий <tex>\ell</tex>, такой, что <tex>B_{j}[\ell']=1</tex>. Заметим, что такой индекс всегда существует  (поскольку<tex> B_{j}[1]=1</tex>) и может быть найден за константное время с использованием битовых операций. Для любого индекса <tex>\ell''\in\{\ell'+1,\ \ldots,\ \ell\}</tex> мы имеем <tex>B_{j}[\ell'']=0</tex>, т.е., случай <tex>(b)</tex> леммы 1 выполняется для <tex>S_{j}^{\ell''}</tex>. Тогда, по индукции, минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>. С другой стороны, <tex>B_{j}[\ell']=1</tex>, поэтому для последнего мы можем гарантировать, что выполняется первый случай леммы, что позволяет нам найти минимальный суффикс <tex>S_{j}^{\ell}</tex> за константное время.
 ===Построение искомой структуры данных===
-Простой алгоритм построения с временем работы <tex>\mathcal{O}(n\log n)</tex> также основывается на Лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти <tex>B_{j}</tex> за <tex>\mathcal{O}(\log n)</tex>. Мы ищем минимальный суффикс <tex>S_{j}^{\ell}</tex> для последовательных значений <tex>\ell</tex>. Как только мы получили результат <tex>\ell-1</tex>, случай <tex>(a)</tex> Леммы 1 даёт нам второго кандидата на минимальный суффикс <tex>S_{j}^{\ell}</tex>, и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем <tex>B_{j}[\ell]=1</tex> если меньший кандидат не содержится в <tex>S_{j}^{\ell-1}</tex>. Стало быть,  мы получили следующий результат:
+Простой алгоритм построения с временем работы <tex>\mathcal{O}(n\log n)</tex> также основывается на лемме 1. Покажем, что построив улучшенный суфмассив, мы можем найти <tex>B_{j}</tex> за <tex>\mathcal{O}(\log n)</tex>. Мы ищем минимальный суффикс <tex>S_{j}^{\ell}</tex> для последовательных значений <tex>\ell</tex>. Как только мы получили результат <tex>\ell-1</tex>, случай <tex>(a)</tex> леммы 1 даёт нам второго кандидата на минимальный суффикс <tex>S_{j}^{\ell}</tex>, и наш улучшенный суфмассив позволяет нам выбрать наименьшего из этих двух кандидатов. Мы устанавливаем <tex>B_{j}[\ell]=1</tex> если меньший кандидат не содержится в <tex>S_{j}^{\ell-1}</tex>. Стало быть,  мы получили следующий результат:
 {{Теорема
@@ Строка 239: / Строка 239: @@
 Чтобы получить структуру данных, со временем построения <tex>\mathcal{O}(n\log n/\tau)</tex> и временем запроса <tex>\mathcal{O}(\tau)</tex>, мы немного по-другому определим битовые вектора. Положим <tex>B_{j}</tex> размером <tex>\lfloor\alpha(1,\ j)/\tau\rfloor</tex>, притом  <tex>B_{j}[k]=1</tex> тогда и только тогда, когда <tex>k=1</tex> или минимальный суффикс <tex>S_{j}^{\tau k}</tex> длиннее, чем <tex>|S_{j}^{\tau(k-1)}|</tex>. В этом случае, нам необходимо только <tex>\mathcal{O}(\log n/\tau)</tex> фаз в алгоритме построения, поэтому он займёт <tex>\mathcal{O}(n\log n/\tau)</tex> времени.
-Как и ранее, предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом {{---}} найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leqslant\ell</tex>, такой, что минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>, но длиннее, чем <tex>|S_{j}^{\ell'-1}|</tex>. Если <tex>\ell=\tau k</tex> для целого <tex>k</tex>, мы можем найти наибольший <tex>k'\leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что <tex>\tau k\leqslant\ell</tex>, и будем знать, что мы должны рассмотреть <tex>\ell'\in(\tau k,\ \ell]</tex> и <tex> \ell'\in(\tau(k'-1),\ \tau k']</tex>, где <tex>k'</tex> определён, как в предыдущем случае. В результате, мы имеем <tex>\mathcal{O}(\tau)</tex> возможных значений <tex>\ell'</tex>, и нам известно, что искомый суффикс может быть найден, используя случай <tex>(a)</tex> Леммы 1 для <tex>S_{j}^{\ell'}</tex> для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за <tex>\mathcal{O}(\tau)</tex>.
+Как и ранее, предположим, что мы ищем минимальный суффикс <tex>T[i..j]</tex>, при <tex>\alpha(i,\ j)=\ell</tex>. Самое сложное в этом {{---}} найти минимальный суффикс <tex>S_{j}^{\ell}</tex>, и далее необходимо найти <tex>\ell'\leqslant\ell</tex>, такой, что минимальный суффикс <tex>S_{j}^{\ell}</tex> на самом деле является минимальным суффиксом <tex>S_{j}^{\ell'}</tex>, но длиннее, чем <tex>|S_{j}^{\ell'-1}|</tex>. Если <tex>\ell=\tau k</tex> для целого <tex>k</tex>, мы можем найти наибольший <tex>k'\leqslant k</tex>, такой, что <tex>B[k']=1</tex>, и нам будет известно, что <tex>\ell'\in(\tau(k'-1),\ \tau k']</tex>. В общем случае, мы выберем наибольший <tex>k</tex>, такой что <tex>\tau k\leqslant\ell</tex>, и будем знать, что мы должны рассмотреть <tex>\ell'\in(\tau k,\ \ell]</tex> и <tex> \ell'\in(\tau(k'-1),\ \tau k']</tex>, где <tex>k'</tex> определён, как в предыдущем случае. В результате, мы имеем <tex>\mathcal{O}(\tau)</tex> возможных значений <tex>\ell'</tex>, и нам известно, что искомый суффикс может быть найден, используя случай <tex>(a)</tex> леммы 1 для <tex>S_{j}^{\ell'}</tex> для каждого из этих значений. Тогда мы просто сгенерируем всех этих кандидатов и используем улучшенный суфмассив, чтобы найти наименьший суффикс среди них. В результате, запрос к нашей структуре данных будет выполняться за <tex>\mathcal{O}(\tau)</tex>.