Cod sursa(job #2454634)

Utilizator ShayVincent Cervoni Shay Data 9 septembrie 2019 16:23:35
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

const int ALPHABET_SIZE = 26;
#define index (*s - 'a')

struct Trie {
	int cnt, nr_fii;
	Trie *fiu[ALPHABET_SIZE];

	Trie() {
		cnt = nr_fii = 0;
		memset(fiu, 0, sizeof(fiu));
	}
};

Trie *trie = new Trie;
void insert(Trie *nod, char *s) {
	if (*s == '\n') {
		++(nod->cnt);
		return;
	}

	if (nod->fiu[index] == 0) {
		nod->fiu[index] = new Trie;
		++(nod->nr_fii);
	}

	insert(nod->fiu[index], s + 1);
}

int remove(Trie *nod, char *s) {
	if (*s == '\n') {
		--(nod->cnt);
	} else if (remove(nod->fiu[index], s + 1)) {
		nod->fiu[index] = 0;
		--(nod->nr_fii);
	}

	if (nod->cnt == 0 && nod->nr_fii == 0 && nod != trie) {
		delete nod;
		return 1;
	}

	return 0;
}

int search(Trie *nod, char *s) {
	if (*s == '\n') {
		return nod->cnt;
	}

	if (nod->fiu[index]) {
		return search(nod->fiu[index], s + 1);
	}

	return 0;
}

int len_pref(Trie *nod, char *s, int k) {
	if (*s == '\n' || nod->fiu[index] == 0) {
		return k;
	}

	return len_pref(nod->fiu[index], s + 1, k + 1);
}

int main() {
	freopen("trie.in", "r", stdin);
	freopen("trie.out", "w", stdout);
	char line[32];

	while (fgets(line, 32, stdin)) {
		switch (line [0]) {
			case '0': insert(trie, line + 2); break;
			case '1': remove(trie, line + 2); break;
			case '2': printf("%d\n", search(trie, line + 2)); break;
			case '3': printf("%d\n", len_pref(trie, line + 2, 0)); break;
			default: break;
		}
	}
	
	return 0;
}