Cod sursa(job #2353666)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 24 februarie 2019 14:41:21
Problema Trie Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

struct trie{
    int nr, c;
    trie *fii[26];
    trie(){
        nr = 0;
        c = 0;
        for(int i=0;i<26;++i)
            fii[i] = NULL;
    }
}*r;

string cmd;

void adauga(trie *& nod, int l){
    if(cmd[l] == '/'){
        nod ->  nr++;
        return ;
    }

    if(nod -> fii[cmd[l]-'a'] == NULL){
        nod -> fii[cmd[l]-'a']  = new trie();
        nod -> c++;
    }

    adauga(nod -> fii[cmd[l]-'a'], l+1);
}

void cauta(trie *& nod, int l){
    if(cmd[l] == '/'){
        cout << nod -> nr<<"\n";
        return ;
    }

    if(nod -> fii[cmd[l]-'a'] == NULL){
        cout << "0\n";
        return ;
    }

    cauta(nod -> fii[cmd[l]-'a'], l+1);

}

bool sterge(trie *& nod, int l){
    if(cmd[l] == '/'){
        nod -> nr --;
        return nod -> nr == 0 && nod -> c == 0;
    }

    if(sterge(nod -> fii[cmd[l]-'a'], l+1)){
        delete nod -> fii[cmd[l]-'a'];
        nod -> fii[cmd[l]-'a'] = NULL;
        nod -> c --;
        return nod -> nr == 0 && nod -> c == 0;
    }

    return 0;

}

void prefix(trie *& nod, int l){
    if(cmd[l] == '/' || nod == NULL){
        cout<<l-3<<"\n";
        return ;
    }

    //cout<<cmd[l];
    prefix(nod -> fii[cmd[l]-'a'], l+1);
}

int main()
{
    freopen("trie.in","r",stdin);
    freopen("trie.out","w",stdout);

    r = new trie();

    do{
        getline(cin,cmd);
        cmd += "/";
        if(cmd[0] == '0'){
            adauga(r, 2);
        }
        else if(cmd[0] == '1'){
            sterge(r, 2);
        }
        else if(cmd[0] == '2'){
            cauta(r, 2);
        }
        else if(cmd[0] == '3'){
            prefix(r, 2);
        }
    }while(!cin.eof());

    return 0;
}