dbndrv 30 марта 2020

Must-have алгоритмы для работы со строками на C++

Алгоритмы на C++ для строковых задач, в которых наивное решение имело бы недопустимую сложность: полиномиальное хеширование, КМП, работа с префиксным деревом и алгоритм Ахо – Корасик.
Must-have алгоритмы для работы со строками на C++

Полиномиальное хеширование

Хеширование строк позволяет эффективно отвечать на вопрос о равенстве строк, сравнивая их хеш-коды. Хеш-код – целое число, вычисляемое по символам строки. Если две строки равны, то их хеш-коды тоже равны.

Рассмотрим полиномиальное хеширование строк, при котором хеш-функция вычисляется как перевод из n-ичной системы в десятичную. Пусть дана строка s, основание BASE и кольцо вычетов по модулю MOD.

Тогда хеш-код строки вычисляется следующим образом:
(s[0] * BASE0 + s[1] * BASE1 + ... + s[n – 1] * BASE(n-1)) % MOD

Или же наоборот:
(s[0] * BASE(n-1) + s[1] * BASE(n-2) + .. + s[n – 1] * BASE0) % MOD

Выбор направления расстановки степеней не принципиален. Главное – использовать такое простое основание BASE, чтобы оно было взаимно простым с MOD, и его значение было больше количества символов в алфавите. MOD также должен быть простым, как правило, он равен 109 + 7 или 109 + 9.

Получение индекса символа s[i] в алфавите. В C++ обычно делают так: (int)s[i] – 'a' + 1. Но чтобы не загрязнять код, можно поступить проще, например, использовать приведение к signed char, который вернёт значение от 0 до 255. Важно помнить, что основание должно быть больше максимального значения возвращаемого кода, поэтому возьмём BASE = 2011 или 2017.

Чтобы иметь возможность получать хеш любой подстроки s[l..r] строки s за O(1), воспользуемся хеш-функцией на префиксах. Рассмотрим её подробнее. Пусть максимальная длина строки – 106. Заведём массив hash[SIZE], хранящий 64-битовые числа. Далее заполняем массив простейшей динамикой по вышеописанным формулам.

        #include <bits/stdc++.h>
 
using namespace std;
 
const int SIZE = 100100;
const int BASE = 2017;
const int MOD = 1000000009;

int64_t hash[SIZE];

void init_hash(const string &line, int64_t *h, int base, int mod)
{
    h[0] = 0;
    int n = line.length();
    for (int i = 1; i <= n; ++i)
    {
        h[i] = h[i - 1] * base % mod + (signed char)line[i - 1] % mod;
    }
}
    

Также понадобится массив степеней выбранного BASE. Заведём powers[SIZE], хранящий 64-битовые числа и заполним его по динамике: powers[i] = powers[i – 1] * BASE % MOD.

        int64_t powers[SIZE];

void init_powers(int64_t *p, int base, int mod)
{
    p[0] = 1;
    for (int i = 1; i < SIZE; ++i)
    {
        p[i] = p[i - 1] * base % mod;
    }
}
    

Рассмотрим получение хеша подстроки. Принцип такой же, как и при запросе суммы на диапазоне. От хеша с индексом r отнимаем хеш с индексом l, умноженный на BASE в степени разности r и l.

        int64_t get_hash(int l, int r, int64_t *h, int64_t *p, int mod)
{
    return (h[r] - h[l] * p[r - l] % mod + mod) % mod;
}
    

Вот и всё, можем пользоваться хешированием. Рассмотрим использование на простой задаче и проверим, что всё работает. Пусть нам даны две строки, a и b, q запросов, в которых даны границы подстрок: l1, r1, l2, r2 для первой и второй строки соответственно. Требуется ответить, равны ли подстроки.

        #include <bits/stdc++.h>
 
using namespace std;
 
const int SIZE = 100100;
const int BASE = 2017;
const int MOD = 1000000009;

int64_t ahash[SIZE];
int64_t bhash[SIZE];

int64_t powers[SIZE];

void init_powers(int64_t *p, int base, int mod)
{
    p[0] = 1;
    for (int i = 1; i < SIZE; ++i)
    {
        p[i] = p[i - 1] * base % mod;
    }
}

void init_hash(const string &line, int64_t *h, int base, int mod)
{
    h[0] = 0;
    int n = line.length();
    for (int i = 1; i <= n; ++i)
    {
        h[i] = h[i - 1] * base % mod + (signed char)line[i - 1] % mod;
    }
}

int64_t get_hash(int l, int r, int64_t *h, int64_t *p, int mod)
{
    return (h[r] - h[l] * p[r - l] % mod + mod) % mod;
}

int main()
{
    string a, b;
    cin >> a >> b;
    init_powers(powers, BASE, MOD);
    init_hash(a, ahash, BASE, MOD);
    init_hash(b, bhash, BASE, MOD);
    int q;
    cin >> q;
    while (q--)
    {
        int al, ar, bl, br;
        cin >> al >> ar >> bl >> br;
        --al; --bl;
        if (get_hash(al, ar, ahash, powers, MOD) == get_hash(bl, br, bhash, powers, MOD))
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
    return 0;
}
    

Теперь поговорим про один серьёзный недостаток полиномиального хеширования, а именно, коллизии. Коллизия – ситуация, когда строки по факту различны, но их хеши совпадают. В таком случае алгоритм заключает, что строки одинаковы, хотя на самом деле это не так.

Избавиться от коллизий при длине строк ~106 невозможно, потому что количество различных строк больше количества различных хеш-кодов. Вероятность коллизии можно свести к минимуму (почти к нулю), если написать ещё один хеш, т. е. написать первый хеш с основанием 2011 по модулю 109 + 7, а второй хеш – с основанием 2017 по модулю 109 + 9 и использовать оба хеша в сравнениях.

Алгоритм Кнута – Морриса – Пратта

Префикс-функция от строки s равна массиву P, где P[i] обозначает максимальную длину собственного (не совпадающего с полной строкой) префикса, равного собственному суффиксу. Говоря простым языком, мы идём по строке слева направо, добавляя s[i], и смотрим: есть ли префикс, совпадающий с суффиксом. Если да, то какова его максимальная длина.

Элементарный пример префикс-функции для строки <code class="inline-code">"abacaba"</code>
Элементарный пример префикс-функции для строки "abacaba"

В определённых случаях префиксы и суффиксы могут перекрываться, как, например, в строке "ABABABA".

Наивный алгоритм нахождения префикс-функции имеет сложность O(N3), что уже неприемлемо для строки длиной хотя бы 103.

Алгоритм Кнута – Морриса – Пратта (КМП) позволяет находить префикс-функцию от строки за линейное время, и имеет довольно лаконичную реализацию, по длине не превышающую наивный алгоритм.

Заметим важное свойство: P[i] <= P[i – 1] + 1. Префикс-функция от следующего элемента превосходит функцию от текущего не более чем на 1. Тогда в 0-индексации верно следующее свойство: s[i] = s[P[i – 1]] => P[i] = P[i – 1] + 1.

Рассмотрим случай, когда s[i] != s[P[i – 1]]: найдём такую длину j, что s[0..j-1] = s[i-j..i-1], но при этом j < P[i – 1]. Если s[i] = s[j], то P[i] = j + 1, тогда j = P[P[i – 1] – 1]. Иначе уменьшаем j по той же формуле: j = P[i – 1]. Пытаемся найти префикс, пока j != 0.

s[14] != s[P[13]]; j = P[P[13] – 1] = 2; s[14] = s[2]; P[14] = j + 1 = 3
s[14] != s[P[13]]; j = P[P[13] – 1] = 2; s[14] = s[2]; P[14] = j + 1 = 3

Теперь можем писать код. Будем использовать 1-индексацию, чтобы не путаться с лишними единицами:

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

const int SIZE = 100100;

int f[SIZE];

int main()
{
    string line;
    cin >> line;
    f[0] = f[1] = 0;
    for (int i = 1; i < line.length(); ++i)
    {
        int current = f[i];
        while (current > 0 && line[current] != line[i])
        {
            current = f[current];
        }

        if (line[i] == line[current])
        {
            f[i + 1] = current + 1;
        }
        else
        {
            f[i + 1] = 0;
        }
    }

    for (int i = 1; i <= line.length(); ++i)
    {
        cout << f[i] << " ";
    }

    return 0;
}
    

Префиксное дерево

Префиксное дерево (также бор, нагруженное дерево, англ. trie) – древовидная структура данных для хранения множества строк. Каждая строка представлена в виде цепочки символов, начинающейся в корне. Если у двух строк есть общий префикс, то у них будет общий корень и некоторое количество общих вершин. Построив префиксное дерево, можно эффективно отвечать на вопрос, содержится ли в множестве данных строк слово, которое нужно найти.

В изображённом боре хранится следующая информация: 7 слов <code class="inline-code">"to",</code> 3 слова <code class="inline-code">"tea"</code>, 4 слова <code class="inline-code">"ted"</code>, 12 слов <code class="inline-code">"ten"</code>, 9 слов <code class="inline-code">"inn"</code>, 5 слов <code class="inline-code">"in"</code>, 11 слов <code class="inline-code">"i"</code> и 15 слов <code class="inline-code">"A"</code>
В изображённом боре хранится следующая информация: 7 слов "to", 3 слова "tea", 4 слова "ted", 12 слов "ten", 9 слов "inn", 5 слов "in", 11 слов "i" и 15 слов "A"

Принято считать, что бор – конечный детерминированный автомат, состояния которого – вершины подвешенного дерева. И правда – когда мы находимся в определённой вершине, т. е. в определённом состоянии, мы можем переместиться в другие по двум параметрам: текущей вершине v и нужному символу c. То есть, мы можем найти такую вершину v', которая обозначает самую длинную строку, состоящую из суффикса текущей вершины v и нужного символа c.

Будем писать бор с использованием структур таким образом, что каждой вершине будет соответствовать объект типа vertex, в котором будут храниться ссылки на следующие объекты (т. е. дочерние вершины) и количество строк, заканчивающихся в текущей вершине. Каждая вершина соответствует определённому символу. Поскольку бор – частный случай автомата, некоторые его вершины будут терминальными, а именно такие вершины, в которых количество заканчивающихся строк больше нуля. Для реализации нам понадобится динамическое выделение памяти.

        #include <bits/stdc++.h>
 
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
struct vertex
{
    vertex* next[ALPHABET_SIZE]; // массив указателей на дочерние вершины
    int strings_amount;
 
    vertex(); // конструктор
};
 
vertex::vertex()
{
    for (int i = 0; i < ALPHABET_SIZE; ++i) // изначально у текущей вершины не существует дочерних
    {
        next[i] = nullptr;
    }
    strings_amount = 0; // и не существует слов, оканчивающихся в ней
}
    

Напишем функцию добавления слова в бор. Корень дерева – root – пустая строка. Если в боре уже есть обрабатываемый символ, просто проходим по нему. Если такового нет – добавляем новую вершину.

        vertex* root = new vertex();
 
void add_string(string &line)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i) // создаём все необходимые вершины, если они ещё не созданы
    {
        int symbol = line[i] - 'a';
        if (current->next[symbol] == nullptr)
        {
            current->next[symbol] = new vertex();
        }
        current = current->next[symbol];
    }
    current->strings_amount++; // увеличиваем кол-во слов, заканчивающихся в последней вершине
}
    

Реализуем проверку на то, содержится ли слово в боре. Алгоритм схож с добавлением. Асимптотика такого поиска будет O(|S|).

        bool has_a_string(string &line)
{
    vertex* current = root; // начинаем идти от вершины
    int n = line.length();
    for (int i = 0; i < n; ++i) // идём по вершинам дерева в соответствии с символами в строке
    {
        current = current->next[line[i] - 'a'];
        if (current == nullptr) // если такого символа нет в дереве, значит, проверяемого слова тоже нет в дереве, выходим
        {
            return false;
        }
    }
    return current->strings_amount > 0;
}
    

Удаление можно реализовать «лениво», пройдясь до терминальной вершины и уменьшив количество слов, оканчивающихся в этой вершине.

        void delete_string(string &line)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i)
    {
        current = current->next[line[i] - 'a'];
        if (current == nullptr)
        {
            return;
        }
    }
    current->strings_amount--;
}
    

Теперь напишем вывод всех слов, содержащихся в дереве. Для этого используем немного модифицированный DFS в сочетании с приёмом рекурсивного перебора.

        string output = "";
 
void output_all_strings(vertex* current = root)
{
    for (int i = 0; i < current->strings_amount; ++i)
    {
        cout << output << "\n";
    }
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        if (current->next[i] != nullptr)
        {
            output.push_back('a' + i);
            output_all_strings(current->next[i]);
            output.pop_back();
        }
    }
}
    

Немного об асимптотике. Как было указано ранее, вставка элемента – O(|Si|), а получение всех ключей – O(k). Это делает бор более эффективной структурой данных по сравнению с обычным деревом, вставка у которого происходит за O(|S|log(k)), и с хеш-таблицей, получение всех ключей которой происходит за O(klog(k)). Но также важно помнить, что в определённых случаях префиксное дерево требует много памяти. Например, когда у всех слов, добавленных в бор, нет пересечений по префиксу, тогда структура будет использовать O(|S||Σ|) памяти, где |S| – сумма длин всех строк, а |Σ| – мощность алфавита.

Полный код:

        #include <bits/stdc++.h>

using namespace std;

const int ALPHABET_SIZE = 26;

struct vertex
{
    vertex* next[ALPHABET_SIZE];
    int strings_amount;

    vertex();
};

vertex::vertex()
{
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        next[i] = nullptr;
    }
    strings_amount = 0;
}

vertex* root = new vertex();

void add_string(string &line)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i) 
    {
        int symbol = line[i] - 'a';
        if (current->next[symbol] == nullptr)
        {
            current->next[symbol] = new vertex();
        }
        current = current->next[symbol];
    }
    current->strings_amount++;
}

void delete_string(string &line)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i)
    {
        current = current->next[line[i] - 'a'];
        if (current == nullptr)
        {
            return;
        }
    }
    current->strings_amount--;
}

bool has_a_string(string &line)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i)
    {
        current = current->next[line[i] - 'a'];
        if (current == nullptr)
        {
            return false;
        }
    }
    return current->strings_amount > 0;
}

string output = "";

void output_all_strings(vertex* current = root)
{
    for (int i = 0; i < current->strings_amount; ++i)
    {
        cout << output << "\n";
    }
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        if (current->next[i] != nullptr)
        {
            output.push_back('a' + i);
            output_all_strings(current->next[i]);
            output.pop_back();
        }
    }
}

int main()
{ 
    int q;
    cin >> q;
    for (int req = 0; req < q; ++req)
    {
        char type;
        cin >> type;
        if (type == '1')
        {
            string word;
            cin >> word;
            add_string(word);
        }
        else if (type == '2')
        {
            string word;
            cin >> word;
            delete_string(word);
        }
        else if (type == '3')
        {
            string word;
            cin >> word;
            has_a_string(word) ? cout << "YES\n" : cout << "NO\n";
        }
        else if (type == '4')
        {
            cout << "\n";
            output = "";
            output_all_strings(root);
        }
    }
    return 0;
}
    

Чтобы лучше понять, как работает префиксное дерево, можете «поиграться» с визуализацией работы структуры данных здесь.

Алгоритм Ахо – Корасик

Пусть дано множество неких строк/паттернов S = {s0, ... si, ... sn} и текст T. Необходимо найти все вхождения строк внутри текста.

Для решения необходимо построить автомат по бору (см. Алгоритм Ахо – Корасик). Мы уже написали функцию поиска строки в боре, которая решает похожую задачу. Но асимптотика такого решения O(n|si|), что неприемлемо.

Для решения поставленной задачи введём понятие суффиксной ссылки. Для начала обозначим, что [u] – строка, по которой мы пришли из корня в вершину u. Суффиксная ссылка вершины u p(u) – это указатель на такую вершину v, что [v] является суффиксом [u] максимальной длины.

Построение суффиксных ссылок

Во-первых, нам необходимо для каждой вершины хранить его предка, чтобы понимать, откуда и по какому символу мы пришли в неё.

Во-вторых, введём понятие перехода. Переход δ(v, c) – переход в боре из вершины v по символу c. В основе алгоритма лежит следующее равенство: p(u) = δ(p(u->parent), cu).

То есть, суффиксная ссылка текущей вершины – переход из вершины, в которую ведёт суффиксная ссылка предка текущей вершины, по символу текущей вершины. Грубо говоря, нужно пойти в предка, посмотреть, куда ведёт суффиксная ссылка (обозначим эту вершину за v'), перейти по ней, а затем попытаться перейти по символу. Если перехода из v' по символу c не существует, то справедливо следующее равенство: δ(v', c) = δ(p(v'), c) , т.е. от вершины, в которую вела суффиксная ссылка предка, нужно ещё раз пройти по суффиксной ссылке, и так вплоть до корня. Если из корня мы не можем перейти по символу c, то пропускаем его. Этот алгоритм справедлив, поскольку суффиксные ссылки всегда ведут в вершину дерева, которое меньше по глубине, следовательно, рано или поздно, мы сможем дойти до корня.

Реализация алгоритма

В каждой вершине помимо того, что мы хранили в обычном боре, будем хранить массив автоматных переходов go, суффиксную ссылку link , предка parent, последний символ parent_char, предыдущий суффикс prev для данной позиции, который является паттерном. Также будем хранить массив ind, который содержит индексы паттернов, оканчивающихся в этой вершине. Выглядит это всё так:

        const int ALPHABET_SIZE = 26;
 
struct vertex
{
    vertex* next[ALPHABET_SIZE];
    vertex* go[ALPHABET_SIZE];
    vertex* link = 0;
    vertex* parent;
    vertex* prev;
    int parent_char;
    vector<int> ind;
 
    vertex();
    vertex(int parent_char, vertex* parent);
};
 
vertex::vertex()
{
    parent_char = 0;
    parent = nullptr;
    prev = nullptr;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        next[i] = nullptr;
        go[i] = nullptr;
    }
}

vertex::vertex(int parent_char, vertex* parent)
{
    this->parent_char = parent_char;
    this->parent = parent;
    prev = nullptr;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        next[i] = nullptr;
        go[i] = nullptr;
    }
}  
    

Добавление паттерна почти такое же, как и в обычном боре:

        vertex* root = new vertex(-1, 0);
 
void add_string(string &line, int ind)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i)
    {
        int symbol = line[i] - 'a';
        if (current->next[symbol] == nullptr)
        {
            current->next[symbol] = new vertex(symbol, current);
        }
        current = current->next[symbol];
    }
    current->ind.push_back(ind);
}
    

Поскольку мы утверждаем, что при использовании суффиксных ссылок, они ведут в меньшее по глубине дерево, суффиксные ссылки и автоматные переходы можно посчитать динамическим программированием. Подсчитывать динамики go и link будем «лениво»: введём для них две функции, которые будут мемоизировать результат выполнения.

        vertex* go(vertex* current, int c);
 
vertex* link(vertex* current)
{
    if (!current->link)
    {
        if (current == root || current->parent == root) // если длина строки < 2, то суффиксная ссылка - корень
        {
            current->link = root;
        }
        else
        {
            current->link = go(link(current->parent), current->parent_char); // в остальных случаях применяем формулу
        }
    }
    return current->link;
}
 
vertex* go(vertex* current, int c)
{
    if (!current->go[c])
    {
        if (current->next[c]) // если обычный переход есть, то автоматный должен вести туда же
        {
            current->go[c] = current->next[c];
        }
        else if (current == root) // если нет перехода из корня, делаем петлю
        {
            current->go[c] = root;
        }
        else
        {
            current->go[c] = go(link(current), c); // в остальных случаях применяем формулу
        }
    }
    return current->go[c];
}
    

Напишем функцию получения суффикса prev, который является паттерном:

        vertex* prev(vertex* current)
{
    if (current == root)
    {
        return nullptr;
    }
    if (!current->prev)
    {
        if (link(current)->ind.size() != 0)
        {
            current->prev = link(current);
        } 
        else
        {
            current->prev = prev(link(current));
        }
    }
    return current->prev;
}
    

Теперь напишем main. Нам нужно ввести n паттернов, добавив их в бор, текст и для каждого паттерна вывести его границы в тексте. Заведём вектор векторов ans, в котором для каждого i-го паттерна будем хранить его правую границу каждого j-го вхождения в текст.

Далее необходимо пройти по тексту, для каждого символа сделать автоматный переход. Каждый паттерн, который оканчивается вершиной, в которую был совершён автоматный переход, добавляем в ans. Пока будет существовать суффикс, prev который будет являться паттерном, будем переходить в него. Затем выведем все вхождения. Код:

        int main() 
{
    int n;
    cin >> n;
    vector<string> patterns;
    for (int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        add_string(s, i);
        patterns.push_back(s);
    }
    string text;
    cin >> text;
    vector<vector<int>> ans(n);
    vertex* cur = root;
    for (int i = 0; i < text.size(); i++) 
    {
        cur = go(cur, text[i] - 'a');
        vertex* cur_ans = cur;
        while (cur_ans) 
        {
            for (int ind: cur_ans->ind)
            {
                ans[ind].push_back(i + 1);
            }
            cur_ans = prev(cur_ans);
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << patterns[i] << " : ";
        int psize = patterns[i].size();
        if (ans[i].size() == 0) 
        {
            cout << "no matching";
        }
        else
        {
            for (int j: ans[i])
            {
                cout << j - psize + 1 << " - " << j << "; ";
            }
        }
        cout << endl;
    }
    return 0;
}
    

Весь код:

        #include <bits/stdc++.h>
 
using namespace std;
 
const int ALPHABET_SIZE = 26;
 
struct vertex
{
    vertex* next[ALPHABET_SIZE];
    vertex* go[ALPHABET_SIZE];
    vertex* link = 0;
    vertex* parent;
    vertex* prev;
    int parent_char;
    vector<int> ind;
 
    vertex();
    vertex(int parent_char, vertex* parent);
};
 
vertex::vertex()
{
    parent_char = 0;
    parent = nullptr;
    prev = nullptr;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        next[i] = nullptr;
        go[i] = nullptr;
    }
}
 
vertex::vertex(int parent_char, vertex* parent)
{
    this->parent_char = parent_char;
    this->parent = parent;
    prev = nullptr;
    for (int i = 0; i < ALPHABET_SIZE; ++i)
    {
        next[i] = nullptr;
        go[i] = nullptr;
    }
}  
 
vertex* root = new vertex(-1, 0);
 
void add_string(string &line, int ind)
{
    vertex* current = root;
    int n = line.length();
    for (int i = 0; i < n; ++i)
    {
        int symbol = line[i] - 'a';
        if (current->next[symbol] == nullptr)
        {
            current->next[symbol] = new vertex(symbol, current);
        }
        current = current->next[symbol];
    }
    current->ind.push_back(ind);
}
 
vertex* go(vertex* current, int c);
 
vertex* link(vertex* current)
{
    if (!current->link)
    {
        if (current == root || current->parent == root)
        {
            current->link = root;
        }
        else
        {
            current->link = go(link(current->parent), current->parent_char);
        }
    }
    return current->link;
}
 
vertex* go(vertex* current, int c)
{
    if (!current->go[c])
    {
        if (current->next[c])
        {
            current->go[c] = current->next[c];
        }
        else if (current == root)
        {
            current->go[c] = root;
        }
        else
        {
            current->go[c] = go(link(current), c);
        }
    }
    return current->go[c];
}
 
vertex* prev(vertex* current)
{
    if (current == root)
    {
        return nullptr;
    }
    if (!current->prev)
    {
        if (link(current)->ind.size() != 0)
        {
            current->prev = link(current);
        } 
        else
        {
            current->prev = prev(link(current));
        }
    }
    return current->prev;
}
 
int main() 
{
    int n;
    cin >> n;
    vector<string> patterns;
    for (int i = 0; i < n; i++) 
    {
        string s;
        cin >> s;
        add_string(s, i);
        patterns.push_back(s);
    }
    string text;
    cin >> text;
    vector<vector<int>> ans(n);
    vertex* cur = root;
    for (int i = 0; i < text.size(); i++) 
    {
        cur = go(cur, text[i] - 'a');
        vertex* cur_ans = cur;
        while (cur_ans) 
        {
            for (int ind: cur_ans->ind)
            {
                ans[ind].push_back(i + 1);
            }
            cur_ans = prev(cur_ans);
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << patterns[i] << " : ";
        int psize = patterns[i].size();
        if (ans[i].size() == 0) 
        {
            cout << "no matching";
        }
        else
        {
            for (int j: ans[i])
            {
                cout << j - psize + 1 << " - " << j << "; ";
            }
        }
        cout << endl;
    }
    return 0;
}
    

Другие задачи на алгоритм Ахо – Корасик:

***

Эта статья написана читателем Библиотеки программиста – не стесняйтесь присылать свои публикации! 🐸 Если статья оказалась для вас трудной, посмотрите наш пост про книги по C++. Cреди перечисляемых есть книги с уклоном на алгоритмы. Больше статей по теме – по тегу Алгоритмы.

МЕРОПРИЯТИЯ

Комментарии

ВАКАНСИИ

Добавить вакансию
Junior QA engineer
Томск, от 45000 RUB до 60000 RUB
Junior Data Engineer
Москва, от 150000 RUB до 190000 RUB

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ