Cod sursa(job #2300963)

Utilizator TooHappyMarchitan Teodor TooHappy Data 12 decembrie 2018 14:20:13
Problema Trie Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.41 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 26;

struct Trie {
    Trie* children[Nmax];
    int appearances, nrChildren;

    Trie () {
        memset(children, 0, sizeof(children));
        nrChildren = appearances = 0;
    }
};

Trie *root = new Trie;

void insert (string word) {
    Trie *current = root;

    for (auto ch: word) {
        Trie *nextNode = current->children[ch - 'a'];
        if (nextNode == NULL) {
            nextNode = new Trie;
            current->nrChildren++;
            current->children[ch - 'a'] = nextNode;
        }

        current = nextNode;
    }
    
    current->appearances++;
}

bool deleteWord (Trie *current, string word, int idx) {
    if (idx == (int)word.size()) {
        current->appearances--;
    } else {
        Trie *nextNode = current->children[word[idx] - 'a'];

        if (deleteWord(nextNode, word, idx + 1) == true) {
            current->children[word[idx] - 'a'] = NULL;
            current->nrChildren--;
        }
    }

    if (current->appearances == 0 && current->nrChildren == 0 && current != root) {
        for (int i = 0; i < Nmax; ++i) {
            delete current->children[i];
        }

        delete[] *(current->children);
        delete current;
        return true;
    }
    
    return false;
}

void deleteWord (string word) {
    deleteWord(root, word, 0);
}

int getAppearances (string word) {
    Trie *current = root;

    for (auto ch: word) {
        Trie *nextNode = current->children[ch - 'a'];

        if (nextNode == NULL) {
            return 0;
        }

        current = nextNode;
    }

    return current->appearances;
}

int getLongestPrefix (string word) {
    Trie *current = root;

    int ans = 0;
    for (auto ch: word) {
        Trie *nextNode = current->children[ch - 'a'];

        if (nextNode == NULL) {
            return ans;
        }

        ++ans;
        current = nextNode;
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);

    int op;
    string word;
    while (in >> op >> word) {
        if (op == 0) {
            insert(word);
        }
        if (op == 1) {
            deleteWord(word);
        }
        if (op == 2) {
            out << getAppearances(word) << "\n";
        }
        if (op == 3) {
            out << getLongestPrefix(word) << "\n";
        }
    }

    in.close(); out.close();

    return 0;
}