Ахо-Корасик не істейді?

Ахо-Корасик — бір text ішінде көп string-ті бірден іздейтін алгоритм.

Мысалы:

patterns:
he
she
his
hers

text:
ushers

Text ішінде кездеседі:

she
he
hers

Неге Ахо-Корасик керек?

Егер әр pattern-ді бөлек KMP немесе Рабин-Карп арқылы іздесек, көп уақыт кетуі мүмкін.

Ахо-Корасик барлық pattern үшін бір автомат құрады. Кейін text бойынша бір рет қана жүреді.

Негізгі идея

Ахо-Корасик — бұл қосымша ссылкалары бар бор.

• tr[v][c] — v вершинасынан c символы бойынша transition
• link[v] — suffix link, mismatch кезінде қайда откат жасаймыз
• cnt[v] — v вершинасында қанша pattern аяқталады
• out[v] — v және suffix link арқылы reachable вершинада қанша pattern аяқталады

Алдымен бор құрамыз

Барлық pattern-дерді борға insert жасаймыз.

Мысалы:

he
she
his
hers

Ортақ prefix-тер бір рет сақталады.

Массив арқылы реализация

Кіші ағылшын әріптері a...z үшін массив қолданамыз:

int tr[N][26];

Негізгі массивтер:

const int N = 1000005;

int tr[N][26];
int link[N];
int cnt[N];
int out[N];
int idx;

Символды санға айналдыру

Егер string тек кіші ағылшын әріптерінен тұрса:

int c = ch - 'a';

Сонда:

Pattern-ді борға қосу

insert бір pattern-ді борға қосады.

void insert(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    cnt[v]++;
}

Соңында cnt[v]++ дегеніміз: осы вершинада бір pattern аяқталды.

Suffix link деген не?

Suffix link — текущая string-тің ең ұзын собственный suffix-іне апаратын ссылка. Бірақ ол suffix борда бар болуы керек.

Мысалы, текущая вершина мына string-ке сәйкес болсын:

she

Оның suffix-тері:

he
e

Егер he борда бар болса, онда she үшін suffix link he-ге барады.

Suffix link қалай құрылады?

Suffix link-тер BFS арқылы root-тан бастап құрылады.

Егер v вершинасынан c символы арқылы u вершинасына өтсек, онда:

link[u] = tr[link[v]][c]

Яғни баланың suffix link-і ата-ананың suffix link-і арқылы табылады.

Автомат құру

build функциясында екі нәрсе жасаймыз:

• suffix link құрамыз
• жоқ transition-дарды толтырамыз

Build-тен кейін tr[v][c] әрқашан дайын болады. Сондықтан text бойынша жүру өте оңай:

v = tr[v][c];

build коды

void build() {
    queue<int> q;

    for (int c = 0; c < 26; c++) {
        int u = tr[0][c];

        if (u != 0) {
            q.push(u);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        out[v] = cnt[v] + out[link[v]];

        for (int c = 0; c < 26; c++) {
            int u = tr[v][c];

            if (u != 0) {
                link[u] = tr[link[v]][c];
                q.push(u);
            } else {
                tr[v][c] = tr[link[v]][c];
            }
        }
    }

    out[0] = cnt[0];
}

out[v] деген не?

out[v] — егер біз text өңдеу кезінде v вершинасында тұрсақ, осы позицияда қанша pattern аяқталғанын көрсетеді.

Pattern:

• тура v вершинасында аяқталуы мүмкін
• немесе suffix link арқылы барған вершинада аяқталуы мүмкін

Формула:

out[v] = cnt[v] + out[link[v]]

Барлық occurrence санын табу

Енді text бойынша бір рет жүреміз.

long long search(string text) {
    int v = 0;
    long long ans = 0;

    for (char ch : text) {
        int c = ch - 'a';

        v = tr[v][c];

        ans += out[v];
    }

    return ans;
}

Әр символ O(1) уақытта өңделеді.

Толық программа: барлық occurrence санын табу

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int tr[N][26];
int link[N];
int cnt[N];
int out[N];
int idx;

void insert(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    cnt[v]++;
}

void build() {
    queue<int> q;

    for (int c = 0; c < 26; c++) {
        int u = tr[0][c];

        if (u != 0) {
            q.push(u);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        out[v] = cnt[v] + out[link[v]];

        for (int c = 0; c < 26; c++) {
            int u = tr[v][c];

            if (u != 0) {
                link[u] = tr[link[v]][c];
                q.push(u);
            } else {
                tr[v][c] = tr[link[v]][c];
            }
        }
    }

    out[0] = cnt[0];
}

long long search(string text) {
    int v = 0;
    long long ans = 0;

    for (char ch : text) {
        int c = ch - 'a';

        v = tr[v][c];

        ans += out[v];
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        insert(s);
    }

    build();

    string text;
    cin >> text;

    cout << search(text);

    return 0;
}

Input / Output

Input

4
he
she
his
hers
ushers

Output

3

Себебі ushers ішінде кездеседі:

she
he
hers

Мысалды түсіндіру

Text:

ushers

Pattern-дер:

he
she
his
hers

Алгоритм she соңындағы e символына келгенде, бірден екі pattern табады:

she
he

Себебі she вершинасының suffix link-і he-ге апарады.

Кейін hers соңында тағы бір pattern табылады:

hers

Табылған pattern id-лерін қалай аламыз?

Егер тек сан емес, нақты қандай pattern табылғанын білу керек болса, terminal вершинада pattern id сақтаймыз.

vector<int> term[N];

Insert кезінде:

void insert(string s, int id) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    term[v].push_back(id);
}

id шығару: қарапайым вариант

Text өңдеу кезінде suffix link бойынша жоғары жүріп, барлық term id-лерін шығарамыз.

void searchIds(string text) {
    int v = 0;

    for (int i = 0; i < (int)text.size(); i++) {
        int c = text[i] - 'a';

        v = tr[v][c];

        int u = v;

        while (u != 0) {
            for (int id : term[u]) {
                cout << "pattern " << id << " ends at " << i << '\n';
            }

            u = link[u];
        }

        for (int id : term[0]) {
            cout << "pattern " << id << " ends at " << i << '\n';
        }
    }
}

Pattern басталу позициясы

Егер pattern i позициясында аяқталса және оның ұзындығы len[id] болса, басталу позициясы:

start = i - len[id] + 1

Сондықтан pattern ұзындықтарын сақтаймыз:

vector<int> len;

Толық версия: pattern id және позиция

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;

int tr[N][26];
int link[N];
int idx;

vector<int> term[N];
vector<int> len;

void insert(string s, int id) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    term[v].push_back(id);
}

void build() {
    queue<int> q;

    for (int c = 0; c < 26; c++) {
        int u = tr[0][c];

        if (u != 0) {
            q.push(u);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int c = 0; c < 26; c++) {
            int u = tr[v][c];

            if (u != 0) {
                link[u] = tr[link[v]][c];
                q.push(u);
            } else {
                tr[v][c] = tr[link[v]][c];
            }
        }
    }
}

void searchIds(string text) {
    int v = 0;

    for (int i = 0; i < (int)text.size(); i++) {
        int c = text[i] - 'a';

        v = tr[v][c];

        int u = v;

        while (u != 0) {
            for (int id : term[u]) {
                int start = i - len[id] + 1;

                cout << id << ' ' << start << '\n';
            }

            u = link[u];
        }

        for (int id : term[0]) {
            int start = i - len[id] + 1;

            cout << id << ' ' << start << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    len.resize(n);

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        len[i] = s.size();

        insert(s, i);
    }

    build();

    string text;
    cin >> text;

    searchIds(text);

    return 0;
}

Тек табылған pattern-дер керек болса

Егер pattern кем дегенде бір рет кездессе болды, found массивін қолдануға болады.

vector<int> found(n);

found[id] = 1;

Text толық өңделгеннен кейін found[id] = 1 болғандарын шығарамыз.

Неге алгоритм жылдам?

Build-тен кейін әр text символы бір transition арқылы өңделеді:

v = tr[v][c];

Сондықтан text бойынша өту O(|text|).

Асимптотика

Мұнда:

Цифрлар үшін автомат

Егер pattern-дер 0...9 цифрларынан тұрса, alphabet size 10 болады.

int tr[N][10];

int c = ch - '0';

Қалған логика сол күйі қалады.

Егер alphabet үлкен болса

Егер символ өте көп болса, tr[N][26] жарамайды. Онда map немесе unordered_map қолдануға болады.

vector<unordered_map<char, int>> tr;

Ахо-Корасик және KMP

Қашан қолданамыз?

Типтік қателер

• Барлық insert-тен кейін build() шақыруды ұмыту
• cnt[v] пен out[v] шатастыру
• build ішінде жоқ transition-дарды толтырмау
• Символ alphabet ішінде емес кезде tr[v][c] қолдану
• N массив size-ын тым кішкентай алу
• Тесттер арасында массивтерді тазаламау
• Root номері 0 екенін ұмыту
• Suffix links құрмай тұрып search жасау

Тесттер арасында автоматты тазалау

Көп test болса, тек қолданылған vertex-терді тазалау жеткілікті.

void clearAho() {
    for (int i = 0; i <= idx; i++) {
        for (int c = 0; c < 26; c++) {
            tr[i][c] = 0;
        }

        link[i] = 0;
        cnt[i] = 0;
        out[i] = 0;
    }

    idx = 0;
}

Қысқа шаблон

const int N = 1000005;

int tr[N][26];
int link[N];
int cnt[N];
int out[N];
int idx;

void insert(string s) {
    int v = 0;

    for (char ch : s) {
        int c = ch - 'a';

        if (tr[v][c] == 0) {
            tr[v][c] = ++idx;
        }

        v = tr[v][c];
    }

    cnt[v]++;
}

void build() {
    queue<int> q;

    for (int c = 0; c < 26; c++) {
        if (tr[0][c] != 0) {
            q.push(tr[0][c]);
        }
    }

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        out[v] = cnt[v] + out[link[v]];

        for (int c = 0; c < 26; c++) {
            int u = tr[v][c];

            if (u != 0) {
                link[u] = tr[link[v]][c];
                q.push(u);
            } else {
                tr[v][c] = tr[link[v]][c];
            }
        }
    }

    out[0] = cnt[0];
}

long long search(string text) {
    int v = 0;
    long long ans = 0;

    for (char ch : text) {
        int c = ch - 'a';

        v = tr[v][c];

        ans += out[v];
    }

    return ans;
}

Ең бастысы