Cod sursa(job #2885051)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 5 aprilie 2022 14:41:42
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50;
char cuvant[NMAX];
int operatie;

struct Trie{
    int cnt,nr_fii;
    Trie *fiu[30];
    Trie(){
        cnt=0;
        nr_fii=0;
        for(int i=0;i<27;i++)
            fiu[i]=NULL;
    }
};

Trie *root = new Trie;

void Bag_cuv(Trie *nod,char *c){
    if(*c==0){
        nod->cnt++;
        return;
    }
    int lit = *c - 'a';
    if(nod->fiu[lit]==NULL){
        nod->fiu[lit]=new Trie;
        nod->nr_fii++;
    }
    Bag_cuv(nod->fiu[lit],c+1);
}

bool Scot_cuv(Trie *nod,char *c){
    if(*c==0){
        nod->cnt--;
    } else {
        int lit = *c - 'a';
        bool ver = Scot_cuv(nod->fiu[lit],c+1);
        if(ver==true){
            nod->fiu[lit]=NULL;
            nod->nr_fii--;
        }
        if(nod->nr_fii == 0 and nod->cnt == 0 and nod!=root){
            delete nod;
            return true;
        }
        return false;
    }
}

int cerinta_2(Trie *nod,char *c){
    if(*c==0) return nod->cnt;
    int lit = *c - 'a';
    if(nod->fiu[lit]!=NULL) return cerinta_2(nod->fiu[lit],c+1);
    return 0;
}

int cerinta_3(Trie *nod,char *c,int depth){
    int lit = *c - 'a';
    if(*c==0 or nod->fiu[lit]==NULL) return depth;
    return cerinta_3(nod->fiu[lit],c+1,depth+1);
}

int main()
{
    while(fin >> operatie >> cuvant){
        if(operatie==0) Bag_cuv(root,cuvant);
        if(operatie==1) Scot_cuv(root,cuvant);
        if(operatie==2) fout << cerinta_2(root,cuvant) << '\n';
        if(operatie==3) fout << cerinta_3(root,cuvant,0) << '\n';
    }
    return 0;
}