Суффиксные структуры

Суффиксный массив: сортировка всех суффиксов строки и что она даёт.

Суффиксный массив — отсортированный список всех суффиксов строки (хранятся, конечно, только их начальные позиции). Он открывает целый класс задач: поиск любого образца за O(m log n), число различных подстрок, наибольшая общая подстрока двух строк. Строить сортировкой «в лоб» — O(n² log n): сравнение суффиксов длинное. Классический трюк — сортировка по степеням двойки: сортируем суффиксы сначала по первым 1, потом 2, 4, 8... символам. На каждом шаге суффикс описывается ПАРОЙ классов эквивалентности с прошлого шага — сравнение пары за O(1).

Попробуйте сами — код можно менять

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::string s;
    std::cin >> s;
    s += "$"; // терминальный символ меньше всех букв
    int n = s.size();

std::vector<int> order(n), cls(n);
    for (int i = 0; i < n; i++) order[i] = i;
    std::sort(order.begin(), order.end(), [&](int a, int b) { return s[a] < s[b]; });
    cls[order[0]] = 0;
    for (int i = 1; i < n; i++) {
        cls[order[i]] = cls[order[i - 1]] + (s[order[i]] != s[order[i - 1]] ? 1 : 0);
    }

for (int len = 1; len < n; len *= 2) {
        std::vector<std::pair<std::pair<int, int>, int>> t(n);
        for (int i = 0; i < n; i++) {
            t[i] = {{cls[i], cls[(i + len) % n]}, i};
        }
        std::sort(t.begin(), t.end());

for (int i = 0; i < n; i++) order[i] = t[i].second;
        cls[order[0]] = 0;
        for (int i = 1; i < n; i++) {
            cls[order[i]] = cls[order[i - 1]] + (t[i].first != t[i - 1].first ? 1 : 0);
        }
    }

std::cout << "Суффиксы по алфавиту:\n";
    for (int i = 1; i < n; i++) { // пропускаем суффикс из одного $
        std::cout << s.substr(order[i], n - 1 - order[i]) << "\n";
    }
    return 0;
}

Входные данные (пример — можно менять)

Суффиксный массив за O(n log² n). Введите: banana

Для banana порядок суффиксов: a, ana, anana, banana, na, nana. Разбор трюков: • терминальный символ $ (меньше любых букв) выравнивает суффиксы до «циклических сдвигов» — поэтому работает (i + len) % n; • класс эквивалентности — «номер группы одинаковых префиксов длины len»; пара (класс начала, класс середины) полностью описывает префикс длины 2·len; • со счётной сортировкой вместо std::sort получается классический O(n log n). Следующий шаг темы — массив LCP (длины общих префиксов соседних суффиксов, алгоритм Касаи за O(n)): с ним считается, например, число различных подстрок. Ещё мощнее — суффиксный автомат, но он ждёт вас после уверенного владения массивом.

Задание: с помощью суффиксного массива banana посчитайте руками число различных подстрок (сумма длин суффиксов минус сумма LCP; ответ: 15). Отметьте урок пройденным.