БОР
Бор — сохтори додаҳо барои нигоҳдории маҷмӯи сатрҳо, ки дарахти овезон бо аломатҳо дар канорҳо мебошад.
Ҳар як қуллаи дарахт сатрро ифода мекунад - ки аз сабти пайдарпайи ҳамаи аломатҳо дар роҳ аз реша то ин қулла иборат аст.
Дар оғоз дарахт аз як қулла (Решаи дарахт) сохта мешавад. Ин қулла сатри холиро ифода мекунад.
Бо қуллаеро ишора мекунем, ки аз қуллаи бо аломати аз рӯи канор ба он мегузарем.
Бигзор сатре бо дарозии бошад, ки мехоҳем илова кунем. Ва . Пас пайдарпай барои ҳар як чунин мекунем:
Дар охир қуллаи сатри -ро ифода хоҳад кард. Метавон ин қулларо ҳамчун терминалӣ ишора кард.
Барои баровардани ҳамаи сатрҳо кофист аз рӯи дарахт гузарем ва ҳамаи сатрҳои қуллаҳои терминалиро барорем.
Барои ёфтани сатри бояд аз рӯи дарахт гузарем ва агар дар ягон лаҳза канор вуҷуд надошта бошад, пас чунин сатр вуҷуд надорад. Дар акси ҳол қуллаи ёфтшударо бармегардонем.
Сатрро дар БОР меёбем ва нишонаи қуллаи терминалӣ-ро мегирем.
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;
}