Cod sursa(job #2353677)

Utilizator alex2kamebossPuscasu Alexandru alex2kameboss Data 24 februarie 2019 14:54:51
Problema Trie Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>

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;
char cmd[30];

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 --;
    }
    else if(sterge(nod -> fii[cmd[l]-'a'], l+1)){
        nod -> fii[cmd[l]- 'a'] = NULL;
        nod -> c --;
    }

    if(nod -> nr == 0 && nod -> c == 0 && nod != r){
        delete nod;
        return 1;
    }

    return 0;

}

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

    if(cmd[l] == '/'){
        cout<<l-2<<"\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();
    while(fgets(cmd, 30, stdin)){
        //getline(cin,cmd);
        //cmd += "/";
        cmd[strlen(cmd)-1] = '/';

        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);
        }
    }

    return 0;
}