Cod sursa(job #3158142)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 17 octombrie 2023 20:53:04
Problema Trie Scor 15
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <fstream>
#include <unordered_map>
#include <string>

using namespace std;

const int SIGMA = 26;

struct trie{
    struct node{
        int val = 0;
        int cnt = 0;
        int number_of_sons = 0;
        node* nxt[SIGMA] = {NULL};
    };

    node *radacina;

    trie(){
        radacina = new node;
        radacina -> val = 1;
    }

    void add(string &s, int poz, node* nod){
        nod -> val++;

        if(poz == s.size()){
            nod -> cnt++;
            return;
        }

        if(nod -> nxt[s[poz] - 'a'] == NULL){
            nod -> number_of_sons++;
            nod -> nxt[s[poz] - 'a'] = new node;
        }

        add(s, poz + 1, nod -> nxt[s[poz] - 'a']);
    }

    void del(string &s, int poz, node* nod){
        nod -> val--;

        if(poz == s.size()){
            nod -> cnt--;

            if(nod -> val == 0 && nod -> number_of_sons == 0){
                delete nod;
            }

            return;
        }

        del(s, poz + 1, nod -> nxt[s[poz] - 'a']);

        if(nod -> nxt[s[poz] - 'a'] == NULL){
            nod -> number_of_sons--;

            if(nod -> val == 0 && nod -> number_of_sons == 0&& nod != radacina){
                delete nod;
            }
        }
    }

    int number_of_apperances(string &s, int poz, node* nod){
        if(poz == s.size()){
            return nod -> cnt;
        }

        if(nod -> nxt[s[poz] - 'a'] == NULL){
            return 0;
        }
        return number_of_apperances(s, poz + 1, nod -> nxt[s[poz] - 'a']);
    }

    void find_longest_common_prefix(string &s, int poz, node* nod, int &candidat){
        if(poz == s.size()){
            return;
        }

        if(nod -> nxt[s[poz] - 'a'] != NULL && nod -> val > 1){
            candidat = poz + 1;
            find_longest_common_prefix(s, poz + 1, nod -> nxt[s[poz] - 'a'], candidat);
        }
    }
};

trie Trie;

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

    string s;
    int op, sol;

    while(fin >> op){
        fin >> s;

        if(op == 0){
            Trie.add(s, 0, Trie.radacina);
        }
        else if(op == 1){
            Trie.del(s, 0, Trie.radacina);
        }
        else if(op == 2){
            fout << Trie.number_of_apperances(s, 0, Trie.radacina) << '\n';
        }
        else{
            sol = 0;
            Trie.find_longest_common_prefix(s, 0, Trie.radacina, sol);

            fout << sol << '\n';
        }
    }

    return 0;
}