Cod sursa(job #2403775)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 11 aprilie 2019 20:47:20
Problema Trie Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("trie.in");
ofstream g("trie.out");

const int SIGMA = 27;

struct Node{
    int prefix;
    int words;
    Node *nei[SIGMA];
};

int mx,lu,i,x,l;
char str[30];
Node *root;

void add(char *str){
    Node *aux = root;
    l = strlen(str);
    for(int i = 0; i < l;++i){
        if(nullptr == aux->nei[str[i] - 'a']){
            Node *newNode = new Node;
            newNode->prefix = 0;
            newNode->words = 0;
            for(int j = 0; j < SIGMA; ++j){
                newNode->nei[j] = nullptr;
            }
            aux->nei[str[i] - 'a'] = newNode;
        }
        aux = aux->nei[str[i] - 'a'];
        aux->prefix++;
    }
    aux->words++;
}
void del(char *str){
    l = strlen(str);
    Node *aux = root;
    for(int i = 0; i < l;++i){
        aux = aux->nei[str[i] - 'a'];
        aux->prefix--;
    }
    aux->words--;
}
int apar(char *str){
    l = strlen(str);
    Node *aux = root;
    for(int i = 0; i < l; ++i){
        if(nullptr == aux->nei[str[i] - 'a']){
            return 0;
        }
        aux = aux->nei[str[i] - 'a'];
    }
    if(nullptr == aux){
        return 0;
    }
    return aux->words;
}
int lung(char *str){
    l = strlen(str);
    Node *aux = root;
    lu = 0;
    i = 0;
    for(i = 0; i < l; ++i){
        if(aux->nei[str[i] - 'a'] == nullptr ||
           aux->nei[str[i] - 'a']->prefix <= 0){
           return lu;
        }
        //cout << aux->prefix << ' ';
        aux = aux->nei[str[i] - 'a'];
        if(aux != root){
            lu ++;
        }
    }
    return lu;
}
int main(){
    root = new Node;
    root->prefix = 0;
    root->words = 0;
    for(int i = 0; i < SIGMA; ++i){
        root->nei[i] = nullptr;
    }
    while(f >> x){
        f.getline(str,30);
        //cout << str << '\n';
        if(x == 0){
            add(str + 1);
        }else if(x == 1){
            del(str + 1);
        }else if(x == 2){
            g << apar(str + 1) << '\n';
        }else if(x == 3){
            g << lung(str + 1) << '\n';
        }
    }
    return 0;
}