August 21, 2017
Пусть задан алфавит $\Sigma$, и на его элементах введено отношение полного порядка. Примерами такого алфавита могут служить латинские буквы с алфавитным порядком или цифры.
Будем говорить, что строка $s$ лексикографически строго меньше строки $p$, если выполнено одно из двух свойств:
Это определение совпадает с житейским понятием алфавитного порядка на словах: меньше то слово, у которого первый несовпадающий символ меньше.
Пусть теперь задана строка $s$ длины $n$. Мы можем выписать все её суффиксы и лексикографически отсортировать их. Каждый суффикс задаётся индексом своего начала, поэтому результат такой сортировки можно записать как перестановку чисел от $0$ до $n-1$. Эта перестановка называется суффиксным массивом строки $s$.
Например, суффиксным массивом строки $abracadabra$ будет перестановка $[10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]$.
Заметим, что длины всех суффиксов различны, поэтому они все попарно неравны, а значит суффиксный массив определён однозначно.
Если бы мы умели сравнивать два суффикса за время $T(n)$, то суффиксный массив можно было бы построить за время $O(n \log n \cdot T(n))$ обычной сортировкой. Сравнение строк за $O(n)$ даёт нам алгоритм за $O(n^2 \log n)$. Но если сравнивать суффиксы с помощью полиномиальный хешей и бинарного поиска, то $T(n) = O(\log n)$ и время построения суффиксного массива составит $O(n \log ^{2} n)$.
Сперва рассмотрим немного другую задачу, хоть и очень похожую. $k$-м циклическом сдвигом строки $s$ назовём строку $s[k:]+s[:k]$, то есть строку, полученную из s переносом первого символа в конец $k$ раз. Наша задача — отсортировать циклические сдвиги строки, то есть построить суффиксный массив, в котором суффиксы рассматриваются как циклические. Циклические сдвиги могут полностью совпадать, поэтому порядок не определён однозначно; нас устроит любой правильный вариант.
Далее в описании алгоритма подразумевается циклическая индексация: $s[n] = s[0]$, $s[l:r] = s[l:] + s[:(r - n)]$, если $(l < n < r < 2 \cdot n)$ и т.д.
Алгоритм будет состоять из нескольких фаз, после $k$-й фазы будут правильно отсортированы циклические подстроки длины $2^{k}$. Очевидно, что после $\lceil \log n \rceil$ фаз будут правильно отсортированы циклические сдвиги. Если каждую фазу выполнять за $O(n)$, то общее время работы алгоритма составит $O(n \log n)$.
Кроме самого порядка сортировки (далее будем называть его суффиксным массивом) мы будем поддерживать разбиение подстрок на классы эквивалентности: для каждой позиции будет храниться номер его класса эквивалентности, одинаковые номера говорят о том, что подстроки, начинающиеся в данных позициях, равны; разные номера — не равны. Более того, меньший номер класса эквивалентности будет у меньшей подстроки.
Нам надо отсортировать подстроки длины $2^0=1$, то есть символы. Это можно было бы сделать и за $O(n \log n)$, не ломая при этом общую асимптотику алгоритма. Однако обычно размер алфавита не превосходит размер строки, поэтому сортировку символов можно сделать подсчётом за $O(n + | \Sigma |)$.
После сортировки надо разбить символы на классы эквивалентности. Для этого мы скажем, что у $0$-го элемента суффиксного массива класс эквивалентности $0$, а потом для каждого следующего элемента суффиксного массива будем проставлять такой же класс, как и предыдущему, если они равны, и на $1$ больший иначе.
Сейчас по плану мы должны отсортировать подстроки длины $2^{k+1}$. Каждая такая подстрока имеет вид $s[p:p+2^{k+1}] = s[p:p+2^{k}] + s[(p+2^{k}):(p+2^{k})+2^{k}]$. То есть сортировка таких подстрок — то же самое, что и сортировка пар из их половинок. Но половинки мы уже отсортировали в предыдущей фазе, и даже присвоили им порядковые номера классов эквивалентности. Поэтому сортировку пар строчек можно заменить на сортировку пар чисел (номеров классов эквивалентности). Для этого можно применить поразрядную сортировку: сначала отсортировать пары по второму элементу, а потом по первому, но уже стабильно. Номера классов эквивалентности у нас до $n$, поэтому сортировать можно подсчётом за $O(n)$. На самом деле, по второму элементу пары мы уже (почти) посортировали в предыдущей фазе: суффиксный массив и является такой сортировкой, только у нас записаны индексы начал именно вторых половин подстрок, а не самих подстрок.
После сортировки нужно снова проставить классы эквивалентности, делать мы будем это так же, как и на нулевой фазе. Конечно, сравнивать на равенство нужно не подстроки длины $2^{k+1}$, а пары номеров старых классов эквивалентности половинок.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
const int N = 100100;
const int A = 26;
int n;
char s[N];
int SA[N], newSA[N];
int classId[N], newClassId[N];
int cnt[N];
void buildSA()
{
for (int i = 0; i <= A; i++)
cnt[i] = 0;
for (int i = 0; i < n; i++)
cnt[(int)(s[i] - 'a') + 1]++;
for (int i = 1; i <= A; i++)
cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++)
SA[cnt[(int)(s[i] - 'a')]++] = i;
classId[SA[0]] = 0;
for (int i = 1; i < n; i++) {
classId[SA[i]] = classId[SA[i - 1]];
if (s[SA[i]] != s[SA[i - 1]])
classId[SA[i]]++;
}
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i <= n; i++)
cnt[i] = 0;
for (int i = 0; i < n; i++) {
int p = (SA[i] - len + n) % n;
cnt[classId[p] + 1]++;
}
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) {
int p = (SA[i] - len + n) % n;
newSA[cnt[classId[p]]++] = p;
}
for (int i = 0; i < n; i++)
SA[i] = newSA[i];
newClassId[SA[0]] = 0;
for (int i = 1; i < n; i++) {
int p1 = SA[i - 1], p2 = SA[i];
int q1 = (p1 + len) % n, q2 = (q2 + len) % n;
newClassId[p2] = newClassId[p1];
if (classId[p1] != classId[p2] || classId[q1] != classId[q2])
newClassId[p2]++;
}
for (int i = 0; i < n; i++)
classId[i] = newClassId[i];
}
}
Казалось бы, суффиксы сравниваются как раз как циклические сдвиги, но это не совсем правда. Суффиксный массив строки $caba$ должен быть $[3, 1, 2, 0]$, а мы построим $[1, 3, 2, 0]$. Для строчки $aaaaa$ правильная сортировка циклических сдвигов — это любая перестановка чисел от $0$ до $4$; в то время как суффиксный массив определён однозначно. В чём же дело?
Причина в том, что если мы сравниваем два суффикса и дошли до конца строчки, то мы должны сразу более короткую из строк объявить меньшей, а вот соответствующие циклические сдвиги мы должны сравнивать дальше. Чтобы эмулировать такое поведение, припишем в конец $s$ символ, который заведомо меньше всех символов $s$. Традиционно в качестве таких символов используют \$ или #. Теперь все циклические сдвиги будут разными (потому что \$ там встречается в разных местах), причём если префиксы двух циклических строк до первого \$ совпадают, то меньше будет тот из них, в котором \$ раньше, то есть тот, который соответствует более короткому суффиксу.
В результате мы получим правильный суффиксный массив, за одним исключением: мы добавили фиктивный суффикс \$, который соответствует пустому суффиксу $s$. Очевидно, что он меньше всех остальных суффиксов, поэтому чтобы его убрать нужно просто удалить начальный элемент суффиксного массива.
Массив LCP — это массив длины $n-1$, $i$-й элемент которого — это длина наибольшего общего префикса (Longest Common Prefix, LCP) суффиксов, начинающихся в позициях $SA[i]$ и $SA[i+1]$, то есть соседних в порядке сортировки.
Было бы неплохо уметь искать длину общего префикса любых двух суффиксов, а не только соседних в каком-то непонятном порядке. Утверждается, что массив LCP может нам в этом сильно помочь.
Рассмотрим два суффикса, у одного позиция в суффиксном массиве — это $p$, у другого — $q$, $p < q$. Пусть их общий префикс имеет длину $L$. Тогда все суффиксы, позиции которых в суффиксном массиве между $p$ и $q$, также будут иметь такой же префикс длины $L$, потому что иначе они не могли бы быть между нашими двумя суффиксами в порядке сортировки. Таким образом, $\forall t \in [p, q) L \le LCP[t]$ Пусть теперь $L’ = min(LCP[p], LCP[p+1], \ldots, LCP[q-1])$. Это значит, что префикс длины $L’$ является общим для суффиксов $SA[p]$ и $SA[p+1]$, и для $SA[p+1]$ и $SA[p+2]$, и т.д. до $SA[q-1]$ и $SA[q]$. Но из этого следует, что для $SA[p]$ и $SA[q]$ префикс длины $L’$ тоже является общим. Отсюда $L \le min(LCP[p], LCP[p+1], \ldots, LCP[q-1]) = L’ \le L$, а значит $L = L’$. Таким образом, чтобы найти LCP двух произвольных суффиксов, нужно просто взять минимум на отрезке массива LCP между позициями вхождений этих суффиксов в суффиксный массив.
Пусть $SA[t] = p$, $SA[t+1] = q$, при этом $LCP[t] ( = LCP(s[p:], s[q:]) ) \ge 2$. Посмотрим теперь на суффиксы с началом в $(p+1)$ и $(q+1)$. Каждый из них получен отбрасыванием первого символа у суффиксов с началами $p$ и $q$, соответственно. Длина этих суффиксов была хотя бы $2$, значит наши суффиксы непустые. У суффиксов с началами в $p$ и $q$ был общий префикс длиной $LCP[t]$, значит у наших суффиксов есть общий префикс длиной хотя бы $LCP[t]-1$. Да что там хотя бы! Мы точно знали, что следующие символы различаются, при этом у суффикса с началом в $p$ следующий символ был меньше (чтобы не думать о конце строчки, будем считать, что там фиктивный \$). Поэтому у суффиксов с началом в $(p+1)$ и $(q+1)$ длина общего префикса ровно $LCP[t]-1$, и суффикс с началом в $(p+1)$ меньше, то есть идёт раньше в суффиксном массиве. Пусть его позиция там — $u$, а позиция суффикса с началом в $(q+1)$ — $v$. Тогда мы знаем, что $min(LCP[u], LCP[u+1], \ldots, LCP[v-1]) = LCP[t] - 1$. Но это значит, что $LCP[u] \ge LCP[t] - 1$.
Отсюда идея алгоритма: будем вычислять массив LCP не в порядке суффиксного массива, а в порядке самих суффиксов. Для реализации нам потребуется перестановка, обратная к суффиксному массиву.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 100100;
int n;
char s[N];
int SA[N];
int revSA[N];
int LCP[N];
void buildLCP()
{
for (int i = 0; i < n; i++)
revSA[SA[i]] = i;
int curLCP = 0;
for (int i = 0; i < n; i++) {
int p = revSA[i];
if (p == n - 1) {
LCP[p] = curLCP = 0;
continue;
}
int q = SA[p + 1];
curLCP--;
if (curLCP < 0) curLCP = 0;
while(i + curLCP < n && q + curLCP < n && s[i + curLCP] == s[q + curLCP])
curLCP++;
LCP[p] = curLCP;
}
}
Единственное место, время работы которого может вызывать сомнения — это внутренний цикл while. Однако заметим, что на каждой его итерации значение $curLCP$ увеличивается на $1$, а количество таких увеличений может превосходить количество уменьшений не более чем на $2n$. Количество уменьшений равно $n$; следовательно, алгоритм работает за $O(n)$ (при условии уже построенного суффиксного массива).
Обычно мы хотим узнавать LCP для любой пары суффиксов. Как мы уже выяснили, для этого нужно брать минимум на отрезке. В данном случае чаще всего для этих целей используют sparse table, так как никаких изменений точно не будет, а на построение суффиксного массива мы все равно уже потратили $O(n \log n)$ времени. Зато на запросы мы будем отвечать за $O(1)$.
Дисклеймер: Настоятельно рекомендуется перед прочтением данного раздела прочитать и осознать построение суффиксного массива строки. Также здесь будут использоваться двоичные подъёмы.
Дан бор (корневое дерево, на каждом ребре которого написан символ некоторого алфавита). Каждой вершине бора сопоставим слово, которое получается прочтением символов на рёбрах, если идти из этой вершины в корень (это отличается от обычного определения, обычно мы идём из корня в вершину). Нужно построить перестановку вершин, которая соответствует лексикографическому порядку соответствующих слов.
Для удобства будем считать, что родитель корня — это сам корень, и на это ребре написан \$. Теперь все строчки стали бесконечными, но их лексикографический порядок не изменился. А теперь будем делать то же, что и при построении обычного суффиксного массива: алгоритм разбивается на $\lceil \log n \rceil$ фаз, после $k$-й фазы правильно отсортированы префиксы длины $2^{k}$. Нулевая фаза не отличается вообще никак.
Как выглядит префикс длины $2^{k+1}$ для строчки, соответствующей вершине $v$? Это префикс длины $2^{k}$, а потом префикс длины $2^{k}$ для вершины, в которую мы придём, если из $v$ $2^{k}$ раз поднимемся в предка. Чтобы определить, что это за вершина, насчитаем двоичные подъёмы. В этом месте мы хотели заменить сортировку строк на сортировку пар номеров классов эквивалентности, а затем сортировать их с помощью поразрядной сортировки. Тут есть проблема, что одна и та же вершина может быть предком на высоте $2^{k}$ для многих вершин, и наш финт “по второму элементу пары мы уже отсортировали на предыдущей итерации” не проходит, придётся честно сортировать сначала по второму элементу, потом по первому, и оба раза подсчётом.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int N = 100100;
const int LOG = 17;
const int A = 26;
int n;
int par[N]; //parent, after k-th iteration will be ancestor (1 << k) levels higher
int newPar[N];
char charToPar[N]; //character on edge to parent
int SA[N], newSA[N];
int classId[N], newClassId[N];
int cnt[N];
void buildSA()
{
//root in vertex 0
charToPar[0] = (char)('a' - 1);
par[0] = 0;
for (int i = 0; i <= A + 1; i++)
cnt[i] = 0;
for (int v = 0; v < n; v++)
cnt[(int)(charToPar[v] - 'a') + 2]++;
for (int i = 1; i <= A + 1; i++)
cnt[i] += cnt[i - 1];
for (int v = 0; v < n; v++)
SA[cnt[(int)(charToPar[v] - 'a') + 1]++] = i;
classId[SA[0]] = 0;
for (int i = 1; i < n; i++) {
classId[SA[i]] = classId[SA[i - 1]];
if (charToPar[SA[i]] != charToPar[SA[i - 1]])
classId[SA[i]]++;
}
for (int len = 1; len < n; len <<= 1) {
for (int i = 0; i <= n; i++)
cnt[i] = 0;
for (int i = 0; i < n; i++) {
int v = SA[i];
int u = par[v];
cnt[classId[u] + 1]++;
}
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) {
int v = SA[i];
int u = par[v];
newSA[cnt[classId[u]]++] = v;
}
for (int i = 0; i <= n; i++)
cnt[i] = 0;
for (int i = 0; i < n; i++) {
int v = newSA[i];
cnt[classId[v] + 1]++;
}
for (int i = 1; i <= n; i++)
cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) {
int v = newSA[i];
SA[cnt[classId[v]]++] = v;
}
newClassId[SA[0]] = 0;
for (int i = 1; i < n; i++) {
int v1 = SA[i - 1], v2 = SA[i];
int u1 = par[v1], u2 = par[v2];
newClassId[v2] = newClassId[v1];
if (classId[v1] != classId[v2] || classId[u1] != classId[u2])
newClassId[v2]++;
}
for (int v = 0; v < n; v++)
classId[v] = newClassId[v];
for (int v = 0; v < n; v++)
newPar[v] = par[par[v]];
for (int v = 0; v < n; v++)
par[v] = newPar[v];
}
}
Дан текст $s$ и шаблон $p$, проверить, правда ли в $s$ есть подстрока, равная $p$.
Построим суффиксный массив строки $s$. Теперь суффиксы отсортированы, и можно бинарным поиском найти самый маленький суффикс, который не меньше $p$. Очевидно, если где-то и будет совпадение, так именно в этом суффиксе. На каждой итерации бинпоиска надо лексикографически сравнивать $p$ с некоторым суффиксом $s$, это можно делать за $O( | p | )$. Общее время работы — $O( | s | \log | s | + | p | \log | s | )$.
Дан текст $s$ и шаблон $p$, проверить, правда ли в $s$ есть подстрока, равная $p$.
Построим строчку $ t = s + \# + p $, где # — символ, который не встречается ни в $s$, ни в $p$. Построим суффиксный массив строки $t$. Найдём в нем суффикс, соответствующий строке $p$. Кандидаты на совпадение из строки $s$ — это ближайшие (в порядке суффиксного массива) слева и справа суффиксы $s$. Найдём их линейным проходом. Осталось проверить, правда ли они подходят. Это можно сделать втупую за $O( | p | )$. Но если посчитан массив $LCP$, то достаточно взять $LCP$ соответствующих суффиксов и сравнить с длиной $p$. $LCP$ можно поддерживать вместе с поиском ближайших слева/справа суффиксов строки $s$. Общее время работы — $O( ( | s | + | p | ) \log ( | s | + | p | ) )$.
Этот метод может показаться сильно (и неоправданно) более сложным, однако он иллюстрирует полезную идею “склейки” строк через разделители.
Дана строка $s$, посчитать количество её различных подстрок.
Построим суффиксный массив строки $s$ и массив $LCP$. Каждая подстрока строки — это префикс некоторого суффикса. Будем обрабатывать суффиксы в порядка суффиксного массива, и прибавлять к ответу количество тех префиксов данного суффикса ($SA[i]$), которых мы ранее не встречали. Какие префиксы мы встречали ранее? Те, у которых длина не больше, чем $LCP$ с каким-то из предыдущих суффиксов. Однако мы знаем, что $LCP$ двух суффиксов — это минимум на отрезке в массиве $LCP$. Поэтому все они ограничены сверху значением $LCP[i-1]$, а одно из значений равно $LCP[i-1]$ (собственно, $LCP$ с предыдущим суффиксом). В итоге нам нужно прибавить к ответу длину суффикса и вычесть $LCP[i-1]$. После всех итераций получаем, что ответ — это $n(n+1)/2 - \sum_{i=0}^{n-2}LCP[i]$ (так как сумма длин всех суффиксов это $n(n+1)/2$). Общее время работы — $O( | s | \log | s | )$.
Дана строка $s$. Найти её подстроку $p$ такую, что $| p | \cdot f(p, s)$ максимально, где $f(p, s)$ — количество вхождений $p$ в $s$.
(внезапно) Построим суффиксный массив строки $s$ и массив $LCP$. Пусть мы зафиксировали подстроку, которую мы хотим взять. Сколько у неё вхождений? Столько, для скольких суффиксов эта подстрока является префиксом. Все такие суффиксы в суффиксном массиве расположены рядом, то есть образуют подотрезок. Пусть теперь мы зафиксировали подотрезок в суффиксном массиве: позиции всех этих суффиксов должны быть вхождениями нашей подстроки. Разумеется, при этом мы хотим максимизировать её длину. Чему она будет равна? — $LCP$ всех этих суффиксов, то есть минимум на соответствующем отрезке в массиве $LCP$.
Теперь зафиксируем только длину ($L$) нашей будущей подстрочки. Мы уже знаем, что нам надо выбрать подотрезок суффиксного массива. Какие подотрезки нам точно нельзя выбирать? — у которых $LCP$ суффиксов строго меньше $L$, то есть в соответствующем отрезке массива $LCP$ есть значения строго меньше $L$. Фактически, такие значения в массиве $LCP$ являются перегородками: мы не можем взять суффиксы по обе стороны от этой перегородки, так как иначе $LCP$ всех суффиксов будет меньше $L$. Такие перегородки разбивают суффиксный массив на хорошие отрезки, и каждый хороший отрезок может обновить ответ своей длиной, умноженной на $L$.
Положим $L = n$, а затем будем его постепенно уменьшать. При этом перегородки будут постепенно исчезать, а хорошие отрезки — склеиваться. Этот процесс можно эмулировать, например, храня хорошие отрезки в std::set (можно обойтись и без каких-либо структур). Перегородок у нас $(n-1)$, поэтому удалений перегородок будет не больше. При уменьшении $L$ ответ для всех старых отрезков только уменьшиться, поэтому пробегаться по всем отрезкам не нужно. Реальные кандидаты на ответ могут появиться только при удалении перегородки, это будет как раз только что созданный хороший отрезок.
Все это может быть реализовано за $O(| s | \log | s | )$.
На самом деле, описаный алгоритм легко доводится до построения суффиксного дерева (по суффиксному массиву).