Cod sursa(job #1044597)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 30 noiembrie 2013 03:09:08
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

struct TrieNode {
    int count;
    unordered_map <char, TrieNode *> letters;
};

TrieNode *trie;

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

void trie_insert(string w) {
    TrieNode *temp_trie = trie;

    for (int i = 0; w[i]; i++) {
        char ch = w[i];
        if (temp_trie->letters.find(ch) != temp_trie->letters.end()) {
            temp_trie = temp_trie->letters[ch];
        }
        else {
            temp_trie->letters[ch] = new TrieNode;
            temp_trie->letters[ch]->count = 0;
            temp_trie = temp_trie->letters[ch];
        }
    }
    temp_trie->count += 1;
}

void trie_remove(string w) {
    TrieNode * temp_trie = trie, *parent;
    for (char ch : w) {
        parent = temp_trie;
        if (temp_trie->letters.find(ch) != temp_trie->letters.end()) {
            temp_trie = temp_trie->letters[ch];
        }
        else {
            return ;
        }
    }

    temp_trie->count -= 1;
    if (temp_trie->count == 0) { // remove key
        parent->letters.erase(w[w.size() - 1]);
    }
}

void trie_print(string w) {
    TrieNode * temp_trie = trie;
    for (char ch : w) {
        temp_trie = temp_trie->letters[ch];
    }
    fout << temp_trie->count << "\n";
}

void trie_prefix(string w) {
    TrieNode * temp_trie = trie;
    int prefix_length = 0;

    for (char ch : w)
        if (temp_trie->letters.find(ch) == temp_trie->letters.end()) {
            fout << prefix_length << "\n";
            return ;
        } else {
            prefix_length += 1;
            temp_trie = temp_trie->letters[ch];
        }
}

int main() {
    int command;
    string w;

    trie = new TrieNode;
    trie->count = 0;

    while (fin >> command >> w) {

        if (command == 0) trie_insert(w);
        else if (command == 1) trie_remove(w);
        else if (command == 2) trie_print(w);
        else if (command == 3) trie_prefix(w);

    }

    return 0;
}