Как построить суффиксный массив за O(n log n) и что он вообще хранит?

Суффиксный массив sa — это перестановка индексов, задающая лексикографический порядок всех суффиксов строки. То есть sa[k] = начало k-го по порядку суффикса. Имея его, можно бинпоиском искать подстроки, считать различные подстроки, и т.д.

Быстрое построение — удвоением (radix/digit sort): сортируем суффиксы по первым 2^k символам, используя ранги предыдущей итерации. На каждом шаге сортировка по паре рангов (rank[i], rank[i+2^{k-1}]). Лог итераций, сортировка за O(n) подсчётом → O(n log n).

vector<int> build_sa(string s) {
    s += '\0';                       // страж, меньше любого символа
    int n = s.size();
    vector<int> sa(n), rnk(n), tmp(n);
    for (int i = 0; i < n; ++i) { sa[i] = i; rnk[i] = s[i]; }
    for (int k = 1; k < n; k <<= 1) {
        auto cmp = [&](int a, int b){
            if (rnk[a] != rnk[b]) return rnk[a] < rnk[b];
            int ra = a+k < n ? rnk[a+k] : -1;
            int rb = b+k < n ? rnk[b+k] : -1;
            return ra < rb;
        };
        sort(sa.begin(), sa.end(), cmp);   // для O(n log n) замените на radix
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; ++i)
            tmp[sa[i]] = tmp[sa[i-1]] + (cmp(sa[i-1], sa[i]) ? 1 : 0);
        rnk = tmp;
    }
    return sa;
}

С std::sort это O(n log^2 n) — обычно проходит до 2·10^5. Для чистого O(n log n) замените сортировку на поразрядную (radix) по двум ключам. Память — O(n).