1632
правки
Изменения
м
rollbackEdits.php mass rollback
=====База рекурсии=====
Если длина текущей строки <tex> S </tex> меньше двухравна двум, надо выполнить обычное сравнение суффиксов.
=====Суффиксный массив для нечетных суффиксов=====
<tex>A_{S}</tex> = []
<font color=green>// Вначале предподсчитаем за O(n) обратную перестановку для суффиксного массива <tex> A_{S_{12}}</tex>, то есть массив rank такой, что <tex> A_{S_{12}}</tex>[rank[i]] = i. // Тогда мы сможем за O(1) сравнивать суффиксы по их позиции.</font>
rank = inverse(<tex>A_{S_{12}}</tex>)
'''while''' i < 2 * n/3 '''and''' j < n/3:
Построим суффиксный массив для строки '''abbacab'''. После добавления защитного символа и дополнения до кратной трем длины, получим '''abbacab$$'''.
* '''Суффиксный массив для позиций не кратных 3'''
# Тройками, соответствующими равными 1 по модулю 3 позициям, будут: '''bba''', '''cab''', '''$$$''', соответствующими равным 2 по модулю 3 — '''bac''', '''cabab$''', '''$$$'''. Новый алфавит <tex> \Sigma' </tex> будет содержать элементы '''bba''', '''cab''', '''$$$''', '''bac''', '''ab$''', которые после сортировки получат номера 3, 4, 0, 2, 1 соответственно.
# Строкой '''bbacab$$$bacab$$$$''' в новом алфавите <tex> \Sigma' </tex> будет <tex> S' </tex> = 340210.
# После рекурсивного вызова получим <tex> A_{S'} </tex> = [5, 2, 4, 3, 0, 1]. Пересчитав <tex> A_{S_{12}} </tex>, получим [(5 - 3)*3 + 2, 2 * 3 + 1, (4 - 3) * 3 + 2, (3 - 3) * 3 + 2, 0 * 3 + 1, 1 * 3 + 1] = [8, 7, 5, 2, 1, 4].
{{Определение
|definition=
'''Разностное покрытие''' (англ. ''difference cover'') <tex> D </tex> по модулю <tex>m </tex> — множество чисел от <tex>0</tex> до <tex>m - 1 </tex> таких, что <tex> \forall i \in [0, m-1]: \exists j, k \in D: i \equiv k - j \pmod m </tex>.
}}
Например, <tex> \{1, 2\} </tex> является разностным покрытием по модулю <tex> 3 </tex>, <tex> \{3, 5, 6\} </tex> является разностным покрытием по модулю <tex> 7 </tex>, а <tex> \{1\} </tex> — не является разностным покрытием по модулю <tex> 2 </tex>, поэтому этот алгоритм не применим к нему. Подробнее узнать, как вычислять разностное покрытие для заданного модуля можно также здесь<ref name="generalisation"/>.
