Cod sursa(job #1314370)

Utilizator tudoras8tudoras8 tudoras8 Data 11 ianuarie 2015 19:56:29
Problema Trie Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <cstring>

#define ALPHABET_SIZE 26

using namespace std;

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

    Trie() {
        cnt = nrfii = 0;
        memset(fiu, NULL, ALPHABET_SIZE);
    }
};

Trie *T = new Trie;

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

    if (nod->fiu[*s - 'a'] == NULL) {
        nod->fiu[*s - 'a'] = new Trie;
        nod->nrfii++;
    }

    ins(nod->fiu[*s - 'a'], s + 1);
}

int del(Trie *nod, char *s) {
    if (*s == '\n') {
        nod->cnt--;
    } else if (del(nod->fiu[*s - 'a'], s + 1)) {
        nod->fiu[*s - 'a'] = NULL;
        nod->nrfii--;
    }

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

int que(Trie *nod, char *s) {
    if (*s == '\n') {
        return nod->cnt;
    }
    if (nod->fiu[*s - 'a']) {
        return que(nod->fiu[*s - 'a'], s + 1);
    }
    return 0;
}

int pre(Trie *nod, char *s, int k) {
    if (*s == '\n' || nod->fiu[*s - 'a'] == NULL) {
        return k;
    }
    return pre(nod->fiu[*s - 'a'], s + 1, k + 1);
}

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

    fgets(line, 32, stdin);
    while (!feof(stdin)) {
        switch(line[0]) {
            case '0': ins(T, line + 2); break;
            case '1': del(T, line + 2); break;
            case '2': printf("%d\n", que(T, line + 2)); break;
            case '3': printf("%d\n", pre(T, line + 2, 0)); break;
        }
        fgets(line, 32, stdin);
    }

    return 0;
}