Trie
Trie — satrlar to‘plamini saqlash uchun ma’lumotlar tuzilmasi bo‘lib, qirralarida belgilar joylashgan osilgan daraxtni ifodalaydi.
Daraxtning har bir cho‘qqisi satrni ifodalaydi — ildizdan ushbu cho‘qqigacha bo‘lgan yo‘ldagi barcha belgilarni ketma-ket yozishdan hosil bo‘ladi.
Boshida bitta cho‘qqidan iborat daraxt yaratiladi (Daraxt ildizi). Bu cho‘qqi bo‘sh satrni ifodalaydi.
deb cho‘qqisidan belgili qirra bo‘ylab o‘tib boradigan cho‘qqini belgilaymiz.
uzunligi bo‘lgan, qo‘shmoqchi bo‘lgan satr bo‘lsin. Va . Unda ketma-ket har bir uchun quyidagini qilamiz:
Oxirida cho‘qqisi satrini ifodalaydi. Bu cho‘qqini terminal deb belgilash mumkin.
Barcha satrlarni chiqarish uchun daraxt bo‘ylab yurib, terminal cho‘qqilarning barcha satrlarini chiqarish kifoya.
satrini topish uchun daraxt bo‘ylab yurish kerak va agar biror paytda qirra mavjud bo‘lmasa, demak bu satr mavjud emas. Aks holda topilgan cho‘qqini qaytaramiz.
Trie - da satrni topamiz va terminal cho‘qqi belgisini olib tashlaymiz.
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;
}