Cod sursa(job #2607441)

Utilizator RG1999one shot RG1999 Data 29 aprilie 2020 19:14:13
Problema Trie Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>

using namespace std;

typedef struct TrieStruct{
    int wordsEnd;
    int wordsContain;
    struct TrieStruct* next[27];
} Trie;

void add_trie(Trie* node, char* word) {
    node->wordsContain++;
    if(!*word) {
        node->wordsEnd++;
        return;
    }
    int index = *word - 'a';
    if(!node->next[index]) {
        node->next[index] = (Trie*)calloc(1, sizeof(Trie));
    }
    add_trie(node->next[index], word + 1);

}

void rm_trie(Trie *node, char *word) {
    node->wordsContain--;
    if(!*word) {
        node->wordsEnd--;
        return;
    }
    int index = *word - 'a';
    rm_trie(node->next[index], word + 1);
    if(node->next[index]->wordsContain == 0) {
        free(node->next[index]);
        node->next[index] = NULL;
    }
}

int app(Trie *node, char *word) {
    if(!*word) {
        return  node->wordsEnd;
    } else {
        int index = *word - 'a';
        return app(node->next[index], word + 1);
    }
}

int find_prefix(Trie *node, char *word) {
    int index = *word - 'a';
    if(!*word || !node->next[index]) {
        return 0;
    } else {
        return 1 + find_prefix(node->next[index], word + 1);
    }
}
int main()
{
    freopen("trie.in", "r", stdin);
    freopen("trie.out", "w", stdout);
    int command;
    char word[21];
    Trie *trie = (Trie*)calloc(1, sizeof(Trie));
    while(!feof(stdin)) {
        scanf("%d %s ", &command, word);
        if(command == 0) {
            add_trie(trie, word);
        }
        if(command == 1) {
            rm_trie(trie, word);
        }
        if(command == 2) {
            printf("%d\n", app(trie, word));
        }
        if(command == 3) {
            printf("%d\n", find_prefix(trie, word));
        }

    }
    return 0;
}