Cod sursa(job #3157572)

Utilizator Paul281881818818181991919191881818Draghici Paul Paul281881818818181991919191881818 Data 15 octombrie 2023 21:48:00
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <cstring>
#include <iostream>
std::ifstream fin("trie.in");
std::ofstream fout("trie.out");

struct Node{
    int terminal = 0, nr_children = 0;
    Node *children[26] = {NULL};
};
Node *Trie;
void add(Node* &trie, char* s, int pos){
    if(pos == strlen(s)){
        trie ->terminal ++;
        return;
    }
    if(trie ->children[s[pos] - 'a'] == NULL){
        Node *node = new Node;
        trie ->children[s[pos] - 'a'] = node;
        trie ->nr_children ++;
    }
    add(trie ->children[s[pos] - 'a'], s, pos + 1);
}
int del(Node* &trie, char *s, int pos){
    if(pos == strlen(s)){
        trie ->terminal --;
        //std::cout << trie ->terminal << "\n";
        if(trie ->terminal == 0 && trie ->nr_children == 0){
            delete trie;
            return 1;
        }
        return 0;
    }
    int val = del(trie ->children[s[pos] - 'a'], s, pos + 1);
    if(val == 1){
        trie -> nr_children --;
        trie ->children[s[pos] - 'a'] = NULL;
    }
    if(trie ->nr_children == 0 && trie ->terminal == 0 && trie != Trie){
        delete trie;
        return 1;
    }
    return 0;
}
int queryap(const Node *trie, char *s, int pos){
    if(pos == strlen(s))
        return trie ->terminal;
    if(trie ->children[s[pos] - 'a']){
        return queryap(trie ->children[s[pos] - 'a'], s, pos + 1);
    }
    return 0;
}
int prefix(const Node* trie, char *s, int pos){
    if(trie ->children[s[pos] - 'a'] == NULL || pos == strlen(s))
        return pos;
    else return prefix(trie ->children[s[pos] - 'a'], s, pos + 1);
}
int main(){
    char s[10001];
    Trie = new Node;
    int op;
    while(fin >> op >> s){
        if(op == 0)
            add(Trie, s, 0);
        else if(op == 1)
            del(Trie, s, 0);
        else if(op == 2)
            fout << queryap(Trie, s, 0) << "\n";
        else
            fout << prefix(Trie, s, 0) << "\n";
    }
}