Cod sursa(job #2454675)

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

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

class Trie {
public:
	int cnt, nr_fii;
	Trie *fiu[ALPHABET_SIZE];

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

	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 != this) {
			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);
	}
};

inline void print(int n) {
	char snum[ALPHABET_SIZE - 1];
	int i = 0;

	do {
		snum[i++] = n % 10 + '0';
		n /= 10;
	} while (n);

	--i;

	while (i >= 0) {
		putchar(snum[i--]);
	}

	putchar('\n');
}


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

	while (fgets(line, 32, stdin)) {
		switch (line [0]) {
			case '0': trie->insert(trie, line + 2); break;
			case '1': trie->remove(trie, line + 2); break;
			case '2': print(trie->search(trie, line + 2)); break;
			case '3': print(trie->len_pref(trie, line + 2, 0)); break;
			default: break;
		}
	}

	return 0;
}