Суффиксный массив

Суффиксный массив

Суффиксный массив, автомат и дерево обобщённо называют суффиксными структурами данных. Они применяются в множестве различных задач, встречающихся как на олимпиадах, так и на практике.

Суффиксные структуры часто (но не всегда) взаимозаменяемые, и более того, конвертируются друг в друга за линейное время. Суффиксный массив — самый простой из них, поэтому мы с него и начнём.

*
«Паблик с тупыми шутками про проганье»

Мотивация

Суффиксным массивом строки \(s\) называется перестановка индексов начал её суффиксов, которая задаёт их порядок в порядке лексикографической сортировки. Иными словами, чтобы его построить, нужно выполнить сортировку всех суффиксов заданной строки.

Как это использовать. Пусть вы решили основать ООО «Ещё Один Поисковик», и чтобы получить финансирование, вы хотите сделат хоть что-то минимально работающие — просто научиться искать по ключевому слову документы, включающие его, а также позиции их вхождения (в 90-е это был бы уже довольно сильный MVP). Простыми алгоритмами (полиномиальными хэшами, z- и префикс-функцией и даже Ахо-Корасиком) это сделать быстро нельзя, а суффиксными структурами — можно.

В случае с суффиксным массивом можно сделать следующее: найти бинарным поиском первый суффикс в суффиксном массиве, который меньше искомого слова, а также последний, который меньше. Все суффиксы между этими двумя будут включать искомую строку как префикс.

Работать такой алгоритм будет за \(O(|t| \log |s|)\), и позже это можно будет оптимизировать до \(O(|t| + \log |s|)\), что является одним из самых оптимальных алгоритмов поиска.

Теперь научимся его строить.

Построение за \(O(n \log n)\)

Для удобства мы допишем в конец строки какой-нибудь символ, который лексикографически меньше любого другого, и будем выполнять сортировку не суффиксов, а циклических сдвигов. Строки мы, соответственно, тоже будем рассматривать циклические. Для стандартной ASCII обычно выбирают либо «$» либо «#», либо просто нулевой символ, если это c-string (в языке Си все строки и так заканчиваются нулевым символом). Легко убедиться, что сортировка таких циклических сдвигов эквивалентна сортировке суффиксов — можно просто убрать всё, что идёт после доллара.

Мы могли бы просто взять перестановку от \(0\) до \(n\), написать компаратор, который сравнивает соответствующие суффиксы, и скормить это в std::sort, что будет работать за \(O(n^2 \log n)\), потому что внутреннее сравнение работает за \(O(n)\). Однако, если сравнивать суффиксы хэшами, то уже тут можно получить \(O(n \log^2 n)\). Но это не самый быстрый и удобный алгоритм.

Наш алгоритм будет состоять из \(\lceil \log n \rceil\) этапов. На \(k\)-том этапе мы будем рассматривать циклические подстроки длины \(2^k\). На последнем этапе мы отсортируем строки длины \(\geq n\) (это легально — они ведь циклические), и мы получим нужный суффиксный массив.

Заметим, что, в отличие сортировки суффиксов, сортировка подстрок не всегда однозначная — они могут быть одинаковыми. Поэтому на каждой фазе алгоритм помимо перестановки \(p\) индексов циклических подстрок мы будем поддерживать для каждой циклической подстроки, начинающейся в позиции \(i\) с длиной 2^k, номер \(c_i\) класса эквивалентности, которому эта подстрока принадлежит (давать их будем таким образом, чтобы они сохраняли порядок: меньшим подстрокам соответствуют меньшие \(c_i\)). Количество классов эквивалентности будем хранить в переменной cls (изначально она равна количеству различных символов).

Пример: \(s = aaba\). Этапов будет 3: для подстрок длины 1, 2 и 4.

\[ p_0 = (0, 1, 3, 2) \;\;\; c_0 = (0, 0, 1, 0) \\ p_1 = (0, 3, 1, 2) \;\;\; c_1 = (0, 1, 2, 0) \\ p_2 = (3, 0, 1, 2) \;\;\; c_2 = (1, 2, 3, 0) \]

Как настоящие программисты, мы нумеруем этапы с нуля, поэтому на нулевом этапе мы отсортируем строки длины \(2^0 = 1\), то есть просто символы. Это мы сделаем сортировкой подсчётом.

Следующие этапы нужно проводить, используя информацию с предыдущих. Можем снова создать перестановку и применить к ней std::sort со своим компаратором.

Как быстро сравнить две подстроки? Мы можем использовать \(c_i\) — каждой строке длины \(2^k\) сопоставить биграмму (строку из двух символов), а именно строка \(s[i..i+2^k-1]\) с точки зрения сортировки будет эквивалентна паре \((c_i, c_{i+2^{k-1}})\). Соответственно, можно просто написать компаратор, который смотрит только на эти пары, и работает за \(O(1)\). Однако, это всё ещё будет работать за \(O(n \log^2 n)\), потому что каждый этап будет работать за \(O(n \log n\)).

Оптимизация до \(O(n \log n)\). Сортировка слиянием оптимальна только тогда, когда мы ничего не знаем про сортиремые значения — в нашем случае это не так. Воспользуемся цифровой сортировкой — сначала отсортируем биграммы по второму символу, а потом по первому. Все вторые элементы уже упорядочены (массив \(p\) с предыдущего этапа). Теперь, чтобы упорядочить их по первому, нам надо просто от каждого элемента в \(p\) отнять \(2^{k-1}\). Таким образом, можно проводить этап за \(O(n)\).

// строка -- это последовательность чисел от 1 до размера алфавита
vector<int> suffix_array (vector<int> &s) {
    s.push_back(0);  // добавляем нулевой символ в конец строки
    int n = (int) s.size(),
        cnt = 0,  // вспомогательная переменная: счётчик для сортировки 
        cls = 0;  // количество классов эквивалентности
    vector<int> c(n), p(n);
    
    map< int, vector<int> > t;
    for (int i = 0; i < n; i++)
        t[s[i]].push_back(i);
    
    // «нулевой» этап
    for (auto &x : t) {
        for (int u : x.second)
            c[u] = cls, p[cnt++] = u;
        cls++;
    }
    
    // пока все суффиксы не стали уникальными
    for (int l = 1; cls < n; l++) {
        vector< vector<int> > a(cls);  // массив для сортировки подсчётом
        vector<int> _c(n);  // новые классы эквивалентности
        int d = (1<<l)/2;
        int _cls = cnt = 0;  // новое количество классов
        
        for (int i = 0; i < n; i++) {
            int k = (p[i]-d+n)%n;
            a[c[k]].push_back(k);
        }
        
        for (int i = 0; i < cls; i++) {
            for (size_t j = 0; j < a[i].size(); j++) {
                // если суффикс начинает новый класс эквивалентности
                if (j == 0 || c[(a[i][j]+d)%n] != c[(a[i][j-1]+d)%n])
                    _cls++;
                _c[a[i][j]] = _cls-1;
                p[cnt++] = a[i][j];
            }
        }
        
        c = _c;
        cls = _cls;
    }
    
    return vector<int>(p.begin()+1, p.end());
}

TODO: переписать это

Наибольшие общие префиксы

Для многих применений очень часто требуется искать длину общих префиксов строк. Например, просто чтобы сравнить две подстроки, мы можем найти их общий префикс и посмотреть на следующий символ — так же, как мы делали с хэшами.

TODO