Cod sursa(job #2089105)

Utilizator CammieCamelia Lazar Cammie Data 16 decembrie 2017 10:55:56
Problema Trie Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <fstream>
#include <cstring>

#define MAXN 32

using namespace std;

ifstream fin("trie.in");
ofstream fout("trie.out");

struct trie{
    int cnt, fr;

    trie *fiu[27];

    trie()
    {
        cnt = 0;
        fr = 0;

        memset(fiu, 0, sizeof(fiu));
    }
};

inline void Add(char *s, trie *t) {
    if (*s == 0) {
        t->cnt++;
        return;
    }
    int delta = *s - 'a';

    t->fr++;

    if (t->fiu[delta] == NULL) {
        t->fiu[delta] = new trie;
    }

    Add(s + 1, t->fiu[delta]);
}

inline void Delete(char *s, trie *t) {
    if (*s == 0) {
        t->cnt--;
        return;
    }

    t->fr--;

    int delta = *s - 'a';

    if (t->fiu[delta] == NULL)
        return;

    Delete(s + 1, t->fiu[delta]);
}

inline int Query(char *s, trie *t) {
    if (*s == 0) {
        return t->cnt;
    }
    int delta = *s - 'a';

    if (t->fiu[delta] == NULL)
        return 0;

    return Query(s + 1, t->fiu[delta]);
}

inline int Prefix(char *s, trie *t) {
    if (t->fr == 1)
        return 0;
    int delta = *s - 'a';

    if (t->fiu[delta] == NULL)
        return 0;
    return Prefix(s + 1, t->fiu[delta]) + 1;
}

trie *root = new trie;

char cuv[MAXN];

inline void Read() {
    int tip;

    fin >> tip >> cuv;

    while (!fin.eof()) {
        if (tip == 0)
            Add(cuv, root);
        else if (tip == 1) {
            Delete(cuv, root);
        }
        else if (tip == 2) {
            fout << Query(cuv, root) << "\n";
        }
        else {
            fout << Prefix(cuv, root) << "\n";
        }

        fin >> tip >> cuv;
    }
 }

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}