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

Построение

Построение за Nlog²N:

vector<int> makeSuffixArray(string s) {
    s += '\0';
    int n = s.size();

    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) { return s[i] < s[j]; });

    vector<int> rank(n);
    rank[p[0]] = 0;
    for (int i = 1; i < n; i++)
        rank[p[i]] = rank[p[i - 1]] + (s[p[i]] != s[p[i - 1]]);

    vector<pair<int, int>> rankPair(n);
    for (int len = 1; len < n; len *= 2) {
        for (int i = 0; i < n; i++)
            rankPair[i] = { rank[i], rank[(i + len) % n] };

        sort(p.begin(), p.end(), [&](int i, int j) { return rankPair[i] < rankPair[j]; });

        rank[p[0]] = 0;
        for (int i = 1; i < n; i++)
            rank[p[i]] = rank[p[i - 1]] + (rankPair[p[i]] != rankPair[p[i - 1]]);
    }

    return p;
}

Построение за NlogN:

Меняем вызов sort() внутри цикла на следующий фрагмент:

for (int i = 0; i < n; i++)
    p[i] = (p[i] - len + n) % n;
countSort(p, rank);

Здесь countSort() — сортировка подсчётом:

void countSort(vector<int> &p, const vector<int> &rank) {
    int n = p.size();

    vector<int> rankCount(n);
    for (int i = 0; i < n; i++)
        rankCount[rank[i]]++;

    vector<int> rankFrom(n);
    for (int i = 1; i < n; i++)
        rankFrom[i] = rankFrom[i - 1] + rankCount[i - 1];

    vector<int> sortedP(n);
    for (int elem : p)
        sortedP[rankFrom[rank[elem]]++] = elem;
    p.swap(sortedP);
}

Поиск подстрок

int lowerBound(const string &s, const vector<int> &p, const string &t) {
    int l = 0, r = p.size();
    while (l + 1 < r) {
        int m = l + (r - l) / 2;
        if (s.compare(p[m], t.size(), t) >= 0)
            r = m;
        else
            l = m;
    }
    return r;
}

int upperBound(const string &s, const vector<int> &p, const string &t) {
    int l = 0, r = p.size();
    while (l + 1 < r) {
        int m = l + (r - l) / 2;
        if (s.compare(p[m], t.size(), t) > 0)
            r = m;
        else
            l = m;
    }
    return r;
}

int count(const string &s, const vector<int> &p, const string &t) {
    return upperBound(s, p, t) - lowerBound(s, p, t);
}

Ссылки

• Codeforces — Суффиксный массив
• e-maxx — Суффиксный массив
• neerc.info.ru/wiki — Суффиксный массив
• Algorithmica.org — Суффиксный массив
• Habr — Суффиксный массив — удобная замена суффиксного дерева
• VisuAlgo — Suffix Array