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

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

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

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

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

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

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

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

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

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

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

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

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

Избавиться от коллизий при длине строк

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

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

Элементарный пример префикс-функции для строки <code />Элементарный пример префикс-функции для строки «abacaba»</p>
<p>В определённых случаях префиксы и суффиксы могут перекрываться, как, например, в строке «ABABABA» .</p>
<p>Наивный алгоритм нахождения префикс-функции имеет сложность O(N 3 ) , что уже неприемлемо для строки длиной хотя бы 10 3 .</p>
<p>Алгоритм Кнута – Морриса – Пратта (КМП) позволяет находить префикс-функцию от строки за линейное время, и имеет довольно лаконичную реализацию, по длине не превышающую наивный алгоритм.</p>
<p>Заметим важное свойство: P[i] <= P[i – 1] + 1 . Префикс-функция от следующего элемента превосходит функцию от текущего не более чем на 1. Тогда в 0-индексации верно следующее свойство: s[i] = s[P[i – 1]] => P[i] = P[i – 1] + 1 .</p>
<p>Рассмотрим случай, когда 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.</p>
<p> <img src=s[14] != s[P[13]]; j = P[P[13] – 1] = 2; s[14] = s[2]; P[14] = j + 1 = 3

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

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

В изображённом боре хранится следующая информация: 7 слов «to», 3 слова «tea» , 4 слова «ted» , 12 слов «ten» , 9 слов «inn» , 5 слов «in» , 11 слов «i» и 15 слов «A»

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

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

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

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

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

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

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

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

Пусть дано множество неких строк/паттернов S = 0, . 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 , который содержит индексы паттернов, оканчивающихся в этой вершине. Выглядит это всё так:

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

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

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

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

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

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

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