Cod sursa(job #2595422)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 7 aprilie 2020 18:37:29
Problema Trie Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <bits/stdc++.h>
using namespace std;

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

struct Trie {
	Trie *Next[27];
	int prefix,cuv;
	Trie(){
        for(int i=0;i<27;i++)
            Next[i]=nullptr;
            prefix=0;
            cuv=0;
    }
};


Trie *rad =new Trie();

void ADD(const string &x){
    Trie *aux=new Trie();
 	aux=rad;
	for (int i=0;i<x.size();i++){
		if(aux->Next[x[i]-'a']==nullptr) {
			aux->Next[x[i]-'a'] = new Trie();
		}
        aux = aux->Next[x[i]-'a'];
        aux->prefix++;
		if(i == x.size()-1){
            aux->cuv++;
		}
	}
}
void REMOVE(const string &x){
    Trie *aux=new Trie();
    aux=rad;
    for(int i=0;i<x.size();i++){
        aux=aux->Next[x[i]-'a'];
        if(aux==nullptr) {
			return;
        }
        aux->prefix--;
		if(i == x.size()-1){
            aux->cuv--;
        }
    }
}
int NUMAR(const string &x){
    Trie *aux=new Trie();
    aux=rad;
    for(int i=0;i<x.size();i++){
        aux=aux->Next[x[i]-'a'];
        if(aux==nullptr){
            return 0;
        }
        if(i==x.size()-1){
            return aux->cuv;
        }
    }

}
int PREFIX(const string &x){
    Trie *aux=new Trie();
    aux=rad;
    int lung=0;
    for(int i=0;i<x.size();i++){
            aux=aux->Next[x[i]-'a'];
        if(aux==nullptr){
            return lung;
        }
        if(aux->prefix>0){
            lung++;
        }
    }
    return lung;
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));
    int n;
    string s;
    while(fin>>n){
        fin>>s;
        if(n==0){
            ADD(s);
        }
        if(n==1){
            REMOVE(s);
        }
        if(n==2){
            fout<<NUMAR(s)<<'\n';
        }
        if(n==3){
            fout<<PREFIX(s)<<'\n';
        }
    }
    return 0;
}