Как найти хэш строки

Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

1. углубишься в решение практических задач;
2. узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.

Ты также будешь на связи с преподавателем и другими студентами.

В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂

***

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

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

Рассмотрим полиномиальное хеширование строк, при котором хеш-функция вычисляется как перевод из 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), воспользуемся хеш-функцией на префиксах. Рассмотрим её подробнее. Пусть максимальная длина строки – 10⁶. Заведём массив 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 << "YESn";
        }
        else
        {
            cout << "NOn";
        }
    }
    return 0;
}
    

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

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

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

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

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

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

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

Заметим важное свойство: 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.

Теперь можем писать код. Будем использовать 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) – древовидная структура данных для хранения множества строк. Каждая строка представлена в виде цепочки символов, начинающейся в корне. Если у двух строк есть общий префикс, то у них будет общий корень и некоторое количество общих вершин. Построив префиксное дерево, можно эффективно отвечать на вопрос, содержится ли в множестве данных строк слово, которое нужно найти.

Принято считать, что бор – конечный детерминированный автомат, состояния которого – вершины подвешенного дерева. И правда – когда мы находимся в определённой вершине, т. е. в определённом состоянии, мы можем переместиться в другие по двум параметрам: текущей вершине 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 << "YESn" : cout << "NOn";
        }
        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;
}
    

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

• Антимат
• Censored!
• I love strings!!
• Электронное правительство

***

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