Skip to content

🔤 Суфиксни структури: Експертно ниво

Суфиксните структури са специализирани инструменти за ефективна обработка на низове. Те позволяват бързи отговори на заявки като "дали низ \(P\) се съдържа в \(S\)", "колко пъти се среща", "намерете най-дългия общ подниз" и др.

Основните структури са: 1. Суфиксно дърво (Suffix Tree). 2. Суфиксен масив (Suffix Array). 3. Суфиксен автомат (Suffix Automaton - SAM).

В състезателното програмиране най-често се използват Суфиксен масив (заради ниската памет и простота) и Суфиксен автомат (заради своята мощност и линейна сложност).

1. Суфиксен масив (Suffix Array)

1.1. Дефиниция

Нека \(S\) е низ с дължина \(n\). Суфиксният масив SA съдържа индексите на всички суфикси на \(S\), сортирани лексикографски. Пример: \(S = "aba"\) Суфикси: 0: "aba" 1: "ba" 2: "a"

Сортирани суфикси: 1. "a" (индекс 2) 2. "aba" (индекс 0) 3. "ba" (индекс 1) \(\implies SA = [2, 0, 1]\).

1.2. Построяване (\(O(N \log N)\))

Най-простият начин е сортиране със std::sort (\(O(N^2 \log N)\)), но е твърде бавно. Ефективният подход използва сортиране чрез класове на еквивалентност на степени на 2.

Идея: 1. Сортираме поднизове с дължина \(2^0 = 1\) (просто символите). 2. Използваме резултата, за да сортираме поднизове с дължина \(2^1 = 2\). Подниз с дължина \(2L\) се състои от два подниза с дължина \(L\): pair(class[i], class[i+L]). 3. Повтаряме до \(2^k \ge n\).

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

using namespace std;

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);

    // Начална фаза (k=0)
    for (int i = 0; i < n; i++) cnt[s[i]]++;
    for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i-1];
    for (int i = 0; i < n; i++) p[--cnt[s[i]]] = i;

    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]]) classes++;
        c[p[i]] = classes - 1;
    }

    // Стъпки (1, 2, 4, ...)
    vector<int> pn(n), cn(n);
    for (int h = 0; (1 << h) < n; ++h) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << h);
            if (pn[i] < 0) pn[i] += n;
        }

        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
        for (int i = 1; i < classes; i++) cnt[i] += cnt[i-1];
        for (int i = n-1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];

        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
            if (cur != prev) ++classes;
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}

vector<int> suffix_array_construction(string s) {
    s += "$"; // Добавяме терминиращ символ (най-малък)
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin()); // Махаме '$'
    return sorted_shifts;
}

1.3. LCP Масив (Longest Common Prefix)

LCP[i] е дължината на най-дългия общ префикс между суфиксите SA[i] и SA[i-1]. Този масив позволява решаването на много задачи. Може да се построи за \(O(N)\) чрез алгоритъма на Касай (Kasai).

Приложения на SA + LCP: 1. Брой различни поднизове: \(\frac{n(n+1)}{2} - \sum LCP[i]\). 2. Най-дълъг повтарящ се подниз: \(\max(LCP)\).

2. Суфиксен автомат (Suffix Automaton - SAM)

2.1. Идея

SAM е ориентиран ацикличен граф (DAG), който компресира всички поднизове на даден низ. * Възли (States): Всеки възел представлява множество от поднизове, които се срещат на едни и същи позиции в \(S\) (т.нар. endpos еквивалентност). * Ребра: Преходи при добавяне на символ. * Suffix Links: Препратки към състоянието, отговарящо на най-дългия суфикс, който е в друг клас на еквивалентност.

2.2. Свойства

  • Брой възли: най-много \(2N - 1\).
  • Брой ребра: най-много \(3N - 4\).
  • Построяване: \(O(N)\) (онлайн алгоритъм).

2.3. Имплементация

Структурата на възела съдържа: * len: дължината на най-дългия подниз в това състояние. * link: суфиксна връзка. * next: map или масив за преходите.

#include <map>

struct State {
    int len, link;
    std::map<char, int> next; // Или масив next[26]
};

const int MAXLEN = 100000;
State st[MAXLEN * 2];
int sz, last;

void sam_init() {
    st[0].len = 0;
    st[0].link = -1;
    st[0].next.clear();
    sz = 1;
    last = 0;
}

void sam_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    st[cur].next.clear();

    int p = last;
    // Следваме суфиксните връзки, докато няма преход с 'c'
    while (p != -1 && st[p].next.find(c) == st[p].next.end()) {
        st[p].next[c] = cur;
        p = st[p].link;
    }

    if (p == -1) {
        st[cur].link = 0;
    } else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) {
            // Лесен случай: просто свързваме
            st[cur].link = q;
        } else {
            // Клониране
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next; // Копираме преходите
            st[clone].link = st[q].link;

            while (p != -1 && st[p].next[c] == q) {
                st[p].next[c] = clone;
                p = st[p].link;
            }
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

2.4. Приложения на SAM

  1. Проверка за срещане на подниз: Тръгваме от корена и следваме ребрата. Ако не можем да направим преход, низът не се среща. Време: \(O(|P|)\).
  2. Брой различни поднизове: Всеки възел \(u\) (освен корена) отговаря на \(len(u) - len(link(u))\) уникални подниза. Сумираме тази разлика за всички възли.
  3. Най-малък цикличен шифт (Lexicographically Minimal String Rotation): Построяваме SAM за низа \(S+S\) и вървим \(N\) стъпки по най-малките лексикографски ребра.
  4. Брой срещания: За всеки възел можем да пресметнем колко пъти се срещат поднизовете му, като "избутаме" броячите от децата към родителите в дървото на суфиксните връзки (link tree).

3. Сравнение

Характеристика Suffix Array + LCP Suffix Automaton
Памет \(O(N)\) (малка константа, int масиви) \(O(N \Sigma)\) или \(O(N)\) с map (по-голяма константа)
Време за строене \(O(N \log N)\) или \(O(N)\) \(O(N)\)
Сложност на имплементация Средна (малко объркваща) Кратка, но абстрактна
Гъвкавост Добра за статични задачи Отлична, поддържа динамично добавяне

За състезания обикновено Suffix Array е предпочитан, ако паметта е ограничена (напр. 256MB за \(N=5 \cdot 10^5\)), докато SAM е по-удобен за задачи с множество различни низове или сложни зависимости.