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

Построение

Построение за 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);
}

Построение массива LCP

vector<int> makeLCP(const string &s, const vector<int> &p) {
    int n = p.size();
    vector<int> positionInP(n);
    for (int i = 0; i < n; i++)
        positionInP[p[i]] = i;

    vector<int> lcp(n);
    for (int i = 0, len = 0; i < n - 1; i++, len = max(len - 1, 0)) {
        int j = p[positionInP[i] - 1];
        while (s[i + len] == s[j + len])
            len++;
        lcp[positionInP[i]] = len;
    }
    return lcp;
}

Количество различных подстрок

long long distinctSubstringsCount(const vector<int> &p, const vector<int> &lcp) {
    long long res = 0;
    for (int i = 1; i < p.size(); i++)
        res += (p.size() - 1 - p[i]) - lcp[i];
    return res;
}

Наибольшая общая подстрока

string longestCommonSubstring(const string &a, const string &b) {
    string s = a + "#" + b;
    auto p = makeSuffixArray(s);
    auto lcp = makeLCP(s, p);

    int len = 0, from = 0;
    for (int i = 1; i < p.size(); i++) {
        if ((p[i] < a.size() && p[i - 1] > a.size() ||
             p[i] > a.size() && p[i - 1] < a.size()) && lcp[i] > len) {
            len = lcp[i];
            from = min(p[i], p[i - 1]);
        }
    }
    return a.substr(from, len);
}

Класс SuffixArray

class SuffixArray {
    string s;
    vector<int> order;

    void radixSort(vector<vector<int>> &rankPair) {
        for (int j : { 1, 0 }) {
            vector<int> count(rankPair.size());
            for (int i = 0; i < rankPair.size(); i++) {
                int rank = rankPair[i][j];
                count[rank]++;
            }

            vector<int> from(rankPair.size());
            for (int rank = 1; rank < rankPair.size(); rank++)
                from[rank] = from[rank - 1] + count[rank - 1];

            vector<int> sortedOrder(order.size());
            for (int i : order) {
                int rank = rankPair[i][j];
                sortedOrder[from[rank]] = i;
                from[rank]++;
            }
            order.swap(sortedOrder);
        }
    }

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

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

public:
    SuffixArray(const string &text) : s(text + '\0') {
        order.resize(s.size());
        for (int i = 0; i < order.size(); i++)
            order[i] = i;
        sort(order.begin(), order.end(), [&](int l, int r) {
            return s[l] < s[r];
        });

        vector<int> rank(s.size());
        rank[order[0]] = 0;
        for (int i = 1; i < s.size(); i++)
            rank[order[i]] = rank[order[i - 1]] + (s[order[i - 1]] != s[order[i]]);

        for (int halfLen = 1; halfLen < s.size(); halfLen *= 2) {
            vector<vector<int>> rankPair(s.size());
            for (int i = 0; i < s.size(); i++)
                rankPair[i] = { rank[i], rank[(i + halfLen) % s.size()] };

            radixSort(rankPair);

            rank[order[0]] = 0;
            for (int i = 1; i < s.size(); i++)
                rank[order[i]] = rank[order[i - 1]] + (rankPair[order[i - 1]] != rankPair[order[i]]);
        }
    }

    int count(const string &word) {
        return upperBound(word) - lowerBound(word);
    }
};

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

Содержание

Построение

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

Построение массива LCP

Количество различных подстрок

Наибольшая общая подстрока

Класс SuffixArray

Ссылки

Навигация