Cod sursa(job #3158147)

Utilizator AnSeDraAndrei Sebastian Dragulescu AnSeDra Data 17 octombrie 2023 21:07:56
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 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] = {};
    };

    node *radacina;

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

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

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

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

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

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

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

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

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

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

    int find_longest_common_prefix(string &s, unsigned int poz, node* nod){
        if(nod -> val == 0){
            return poz - 1;
        }

        if(poz == s.size()){
            return poz;
        }

        if(nod -> nxt[s[poz] - 'a'] == 0){
            return poz;
        }

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

trie Trie;

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

    string s;
    int op;

    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{
            fout << Trie.find_longest_common_prefix(s, 0, Trie.radacina) << '\n';
        }
    }

    return 0;
}