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

2020-03-31 12:02

теория программирования, Теория алгоритмов

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

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

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

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

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

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

Выбор направления расстановки степеней не принципиален. Главное – использовать такое простое основание BASE, чтобы оно было взаимно простым с MOD, и его значение было больше количества символов в алфавите. MOD также должен быть простым, как правило, он равен 10⁹ + 7 или 10⁹ + 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 запросов, в которых даны границы подстрок: l₁, r₁, l₂, r₂ для первой и второй строки соответственно. Требуется ответить, равны ли подстроки.

             #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 ";         }         else         {             cout << "NO ";         }     }     return 0; }

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

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

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

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

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

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

Наивный алгоритм нахождения префикс-функции имеет сложность O(N³), что уже неприемлемо для строки длиной хотя бы 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.

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 << " ";     }     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(|S_i|), а получение всех ключей – 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 << " ";     }     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 " : cout << "NO ";         }         else if (type == '4')         {             cout << " ";             output = "";             output_all_strings(root);         }     }     return 0; }

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

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

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

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

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

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

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

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

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

Источник: proglib.io

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

Комментарии: