БОР
Бор — структура данных для хранения набора строк, представляющая собой подвешенное дерево с символами на рёбрах.
Каждая вершина дерева представляет собой строку - состоящая последовательной записью всех символов на пути от корня к данной вершине.
В начале создается дерево из одной вершины (Корень дерева). Эта вершина представляет пустую строку.
Обозначим как вершину к которой пройдем по ребру из вершины с символом .
Пусть это строка длиной которую хотим добавить. А . Тогда последовательно для каждого делаем следующее:
В конце вершина будет представлять собой строку . Можно обозначить эту вершину как терминальную.
Для вывода всех строк достаточно пройтись по дереву и вывести все строки терминальных вершин.
Для нахождения строки надо пройтись по дереву и если в какой-то момент не существует ребра, то данной строки не существует. Иначе возвращаем найденную вершину.
Находим строку в БОР-е и убираем марку терминальная вершина.
int G;
int edge[N][26];
int terminal[N];
void init() {
G = 0;
for (int i = 0; i < N; i++) {
terminal[i] = 0;
for (int j = 0; j < 26; j++) {
edge[i][j] = 0;
}
}
}
void add_string(string s) {
int x = 0;
for (char c: s) {
int g = c - 'a';
if (!edge[x][g]) {
edge[x][g] = ++G;
}
x = edge[x][g];
}
terminal[x] += 1;
}
int find_string(string s) {
int x = 0;
for (char c: s) {
int g = c - 'a';
if (!edge[x][g]) {
return -1;
}
x = edge[x][g];
}
return x;
}