Алгоритмы на строках

А. Климовский

Рассмотрим следующую простую задачу: реализовать множество строк (операции добавление, удаление и поиск). С этой задачей успешно справляется структура данных бор. Вместо того чтобы давать строгое определение, лучше рассмотрим, как он работает.

Заведем корневое дерево, у которого на каждом ребре написан символ алфавита. Из каждой вершины дерева существует ребро к потомкам, если и только если в том поддереве есть элементы. Каждая вершина соответствует строке, получающейся на пути от корня до этой вершины. Например, вершинам на рис. 1 соответствуют строки “”, “a”, “b”, “bx” (пустая строка соответствует корню). Это только строки, которые соответствуют вершинам, а не элементы реализуемого множества.

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

Иногда бывает удобно по-другому маркировать элементы множества: заканчивать строки некоторым терминальным символом (например “$”). Здесь мы так делать не будем.