Алгоритм Касаи и др. - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:30Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:05, 1 сентября 2022

2022-09-01T04:05:06Z

178.234.40.81: /* Псевдокод */

2019-07-27T13:34:07Z

‎Псевдокод

46.183.217.186 в 13:57, 8 июня 2016

2016-06-08T13:57:02Z

46.183.217.186 в 13:46, 8 июня 2016

2016-06-08T13:46:56Z

46.183.217.186 в 11:24, 8 июня 2016

2016-06-08T11:24:43Z

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

46.183.217.186 в 10:40, 8 июня 2016

2016-06-08T10:40:31Z

46.183.217.186 в 10:28, 8 июня 2016

2016-06-08T10:28:36Z

46.183.217.186 в 10:24, 8 июня 2016

2016-06-08T10:24:03Z

46.183.217.186 в 10:23, 8 июня 2016

2016-06-08T10:23:05Z

← Предыдущая		Версия 16:35, 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 Майкл Наки].
−	\|}
−
	'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.		'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.

← Предыдущая		Версия 04:05, 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 Майкл Наки].
		+	\|}
		+
	'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.		'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.

@@ Строка 132: / Строка 132: @@
            lcp[n - 1] <tex>=</tex> -1
            k <tex>=</tex> 0
         '''else'''
            '''int''' j <tex>=</tex> suf[pos[i] + 1]

@@ Строка 1: / Строка 1: @@
-'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних циклических сдвигов строки, отсортированных в лексикографическом порядке.
+'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних суффиксов строки, отсортированных в лексикографическом порядке.
 ==Обозначения==
@@ Строка 8: / Строка 8: @@
 * <tex>Suf^{-1}</tex> {{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
 * <tex>LCP(S_{Suf[x]}, S_{Suf[z]})</tex> {{---}} длина наибольшего общего префикса строк <tex>S_{Suf[x]}</tex> и <tex>S_{Suf[z]}</tex>.
-* <tex>lcp[i]</tex> {{---}} длина наибольшего общего префикса соседних строк, то есть <tex>lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})</tex>.
+* <tex>lcp[i]</tex> {{---}} длина наибольшего общего префикса соседних строк <tex>i-1</tex> и <tex>i</tex>, то есть <tex>lcp[i] = LCP(S_{Suf[i-1]}, S_{Suf[i]})</tex>.
 ==Некоторые свойства LCP==
@@ Строка 39: / Строка 39: @@
 ===Пример===
-[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к факту 2 и 3]]
+[[Файл:kasai.png|400px|thumb|right|Пояснительная картинка к утверждениям 2 и 3]]
 Рассмотрим строку <tex>S = aabaaca\$</tex>. Её суффиксный массив:
 {| class="wikitable"
@@ Строка 101: / Строка 101: @@
 Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.
 |proof=
-Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из факта №1
+Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из [[#fact2 | утверждения №2]]. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из [[#fact1 | утверждения №1]].
 }}

@@ Строка 1: / Строка 1: @@
-'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить
+'''Алгоритм Касаи, Аримуры, Арикавы, Ли, Парка''' (англ. ''Kasai, Arimura, Arikawa, Lee, Park algorithm'') {{---}} алгоритм, позволяющий за линейное время вычислить длину наибольших общих префиксов (англ. ''longest common prefix'', ''LCP'') для всех соседних циклических сдвигов строки, отсортированных в лексикографическом порядке.
 ==Обозначения==
-Нам даны:
+Введём следующие обозначения:
-* Строка <tex>S</tex>, тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе.
+* <tex>S</tex> {{---}} данная строка.
-* [[Суффиксный массив | Суффиксный массив]] <tex>Suf</tex>.
+* <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе.
-* Массив, обратный суффиксному,  <tex>Suf^{-1}</tex>, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>
+* <tex>Suf</tex> {{---}} [[Суффиксный массив | суффиксный массив]].
+* <tex>Suf^{-1}</tex> {{---}} массив, обратный суффиксному, который может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
-Пусть у нас есть массив <tex>lcp</tex>, такой что <tex>lcp[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).
+* <tex>LCP(S_{Suf[x]}, S_{Suf[z]})</tex> {{---}} длина наибольшего общего префикса строк <tex>S_{Suf[x]}</tex> и <tex>S_{Suf[z]}</tex>.
 ==Некоторые свойства LCP==
@@ Строка 15: / Строка 14: @@
 |id = fact1
 |about= №1
-|statement=<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>
+|statement=
-}}
+<tex>LCP(S_{Suf[y - 1]}, S_{Suf[y]}) \geqslant LCP(S_{Suf[x]},S_{Suf[z]}), x < y \leqslant z</tex>
 <tex>LCP</tex> между двумя суффиксами {{---}} минимум <tex>LCP</tex> всех пар соседних суффиксов между ними в суффиксном массиве <tex>Suf</tex>. То есть <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{x < y \leqslant z}LCP(S_{Suf[y - 1]},S_{Suf[y]})</tex>.
 Отсюда следует, что <tex>LCP</tex> пары соседних суффиксов в массиве <tex>Suf</tex> больше или равно <tex>LCP</tex> пары суффиксов, окружающих их.
+}}
+Также заметим, что <tex>LCP(S_{Suf[x]}, S_{Suf[z]}) = \min\limits_{i = x + 1 \ldots z}lcp[i]</tex>.
 {{Утверждение
 |id = fact2
@@ Строка 26: / Строка 26: @@
 |statement=
 Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]}) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex>
 }}
 {{Утверждение
@@ Строка 34: / Строка 34: @@
 |about= №3
 |statement=Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>LCP(S_{Suf[x-1]+1} , S_{Suf[x]+1}) = LCP(S_{Suf[x-1]} , S_{Suf[x]} ) - 1</tex>
 }}
 ===Пример===
@@ Строка 94: / Строка 94: @@
 ===Вспомогательные утверждения===
-Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>\mathrm{lcp}[q]</tex>, когда задано <tex>\mathrm{lcp}[p]</tex>.
+Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>lcp[q]</tex>, когда задано <tex>lcp[p]</tex>.
-{{Лемма|statement=
+{{Лемма
 Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.
 |proof=
@@ Строка 105: / Строка 107: @@
 Если <tex>lcp[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>lcp[q] = LCP(S_{k}, S_{i}) \geqslant lcp[p] - 1</tex>
 |proof=
-<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (по лемме).
+<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (по [[#lemma | лемме]]).
 <tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (по [[#fact3 | утверждению №3]]).

@@ Строка 83: / Строка 83: @@
 | <tex>\bot</tex> || <tex>0</tex> || <tex>1</tex> || <tex>2</tex> || <tex>1</tex> || <tex>1</tex> || <tex>0</tex> || <tex>0</tex>
 |}
-Например <tex>\mathrm{Height}[3] = 2</tex> {{---}} это длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>
+Например <tex>\mathrm{Height}[3] = 2</tex> {{---}} это длина наибольшего общего префикса <tex>aa</tex> суффиксов <tex>S_{Suf[2]} = aabaaca\$</tex> и <tex>S_{Suf[3]} = aaca\$</tex>.
 ===Вспомогательные утверждения===
-Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>\mathrm{Height}[q]</tex>, когда задано <tex>\mathrm{Height}[p]</tex>
+Теперь рассмотрим следующую задачу: рассчитать <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf</tex>, при условии, что значение <tex>LCP</tex> между <tex>S_{i-1}</tex> и его соседним суффиксом известны. Для удобства записи пусть <tex>p=Suf^{-1}[i - 1]</tex> и <tex>q = Suf^{-1}[i]</tex>. Так же пусть <tex>j - 1 = Suf[p-1]</tex> и <tex>k = Suf[q - 1]</tex>. Проще говоря, мы хотим посчитать <tex>\mathrm{Height}[q]</tex>, когда задано <tex>\mathrm{Height}[p]</tex>.
 {{Лемма|statement=
-Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>
+Если <tex>LCP(S_{j-1}, S_{i-1}) > 1</tex>, тогда <tex>LCP(S_k,S_i) \geqslant LCP(S_j,S_i)</tex>.
 |proof=
 Так как <tex>LCP(S_{j-1},S_{i-1}) > 1</tex>, имеем <tex>Suf^{-1}[j] < Suf^{-1}[i]</tex> из факта №2. Так как <tex>Suf^{-1}[j] \leqslant Suf^{-1}[k] = Suf^{-1}[i] - 1</tex>, имеем <tex>LCP(S_{k} , S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> из факта №1
@@ Строка 97: / Строка 97: @@
 Если <tex>\mathrm{Height}[p] = LCP(S_{j-1}, S_{i-1}) > 1</tex>, то <tex>\mathrm{Height}[q] = LCP(S_{k}, S_{i}) \geqslant \mathrm{Height}[p] - 1</tex>
 |proof=
-<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммы)
+<tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j} , S_{i})</tex> (из леммы).
 <tex>LCP(S_{j} , S_{i}) = LCP(S_{j-1}, S_{i-1}) - 1</tex> (из факта №3).
-Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>
+Значит, <tex>LCP(S_{k}, S_{i}) \geqslant LCP(S_{j-1}, S_{i-1}) - 1</tex>.
 }}

@@ Строка 109: / Строка 109: @@
 ===Псевдокод===
 Алгоритм принимает на вход строку с добавленным специальным символом <tex>\$</tex> и суффиксный массив этой строки, и возвращает массив <tex>lcp</tex>, такой что <tex>lcp[i]</tex> содержит длину наибольшего общего префикса строк <tex>i</tex> и <tex>i-1</tex> в суффиксном массиве.
-  '''int[]''' buildLCP(str: '''string''', suf: '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font>
+  '''int[]''' buildLCP(str: '''string''', suf: '''int[]''')
      '''int''' len <tex>=</tex> str.length
      '''int[len]''' lcp
-     '''int[len]''' pos                            <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
+     '''int[len]''' pos  <font color=green> // pos[] {{---}} массив, обратный массиву suf </font>
      '''for''' i = 0 '''to''' len - 1
         pos[suf[i]] <tex>=</tex> i

@@ Строка 4: / Строка 4: @@
 ==Обозначения==
-Задана строка <tex>S</tex>. Тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>Suf</tex>. Для вычисления <tex>LCP</tex> будем использовать промежуточный массив <tex>Suf^{-1}</tex>. Массив <tex>Suf^{-1}</tex> определен как обратный к массиву <tex>Suf</tex>. Он может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
+Задана строка <tex>S</tex>. Тогда <tex>S_{i}</tex> {{---}} суффикс строки <tex>S</tex>, начинающийся в <tex>i</tex>-ом символе. Пусть задан суффиксный массив <tex>Suf</tex>. Для вычисления <tex>LCP</tex> будем использовать вспомогательный массив <tex>Suf^{-1}</tex>. Массив <tex>Suf^{-1}</tex> определен как обратный к массиву <tex>Suf</tex>. Он может быть получен немедленно, если задан массив <tex>Suf</tex>. Если <tex>Suf[k] = i</tex>, то <tex>Suf^{-1}[i] = k</tex>.
-<tex>\mathrm{Height}[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).
+Пусть <tex>\mathrm{Height}</tex> {{---}} массив <tex>LCP</tex>, тогда <tex>\mathrm{Height}[i]</tex> {{---}} длина наибольшего общего префикса <tex>i</tex> и <tex>i-1</tex> строк в суффиксном массиве (<tex>Suf[i]</tex> и <tex>Suf[i-1]</tex> соответственно).
 ==Некоторые свойства <tex>LCP</tex>==
@@ Строка 18: / Строка 18: @@
 ===Факт №2===
-Если значение <tex>LCP</tex> между парой суффиксов, соседних в массиве <tex>Suf</tex>, больше <tex>1</tex>, то можно удалить первый символ каждого суффикса и лексикографический порядок суффиксов сохранится.<br>
+Рассмотрим пару суффиксов, соседних в массиве <tex>Suf</tex>. Тогда если их значение <tex>LCP</tex> больше <tex>1</tex>, то можно удалить первый символ этих суффиксов и их лексикографический порядок относительно друг друга сохранится. То есть строка <tex>S_{Suf[x] + 1}</tex> будет идти следом за строкой <tex>S_{Suf[x-1] + 1}</tex> и останется лексикографически больше нее.
 {{Утверждение
 |statement=
-Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]} ) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex>
+Если <tex>LCP(S_{Suf[x-1]} , S_{Suf[x]}) > 1</tex>, тогда <tex>Suf^{-1}[Suf[x - 1] + 1] < Suf^{-1}[Suf[x] + 1]</tex>
 }}
 ===Факт №3===
@@ Строка 31: / Строка 30: @@
 }}
 ===Вспомогательные утверждения===
@@ Строка 51: / Строка 105: @@
 }}
-==Описание алгоритма и псевдокод==
+==Алгоритм==
-Таким образом, начиная проверять <tex>LCP</tex> для текущего суффикса не с первого символа, а с указанного, можно за линейное время построить <tex>LCP</tex>.
+Представим алгоритм <tex>\mathrm{buildLCP}</tex> который вычисляет массив <tex>LCP</tex>, зная суффиксный массив. Исходя из выше написанной теоремы, нам не нужно сравнивать все символы, когда мы вычисляем <tex>LCP</tex> между суффиксом <tex>S_{i}</tex> и его соседним суффиксом в массиве <tex>Suf^{-1}</tex>. Чтобы вычислить <tex>LCP</tex> всех соседних суффиксов в массиве <tex>Suf^{-1}</tex> эффективно, будем рассматривать суффиксы по порядку начиная с <tex>S_1</tex> и заканчивая <tex>S_n</tex>.
   '''int[]''' buildLCP(str: '''string''', suf: '''int[]''') <font color=green> // str {{---}} исходная строка с добавленным специальным символом $ </font>
                                              <font color=green> // suf[] {{---}} суффиксный массив строки str </font>
@@ Строка 77: / Строка 130: @@
            lcp[pos[i]] <tex>=</tex> k
      '''return''' lcp
 == См. также ==