Cod sursa(job #2381073)

Utilizator dan.ghitaDan Ghita dan.ghita Data 15 martie 2019 23:15:20
Problema Trie Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <bits/stdc++.h>
#include <unordered_map>

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

class TrieNode
{
    unordered_map<char, TrieNode*> children;
    int cnt = 0;

public:
    void insert(string s, int index = 0)
    {
        if (index == s.size())
        {
            ++cnt;
            return;
        }

        if (children.find(s[index]) == children.end())
            children[s[index]] = new TrieNode();

        children[s[index]]->insert(s, index + 1);
    }

    bool remove(string s, int index = 0)
    {
        if (index == s.size())
        {
            --cnt;
            return cnt <= 0 && children.empty();
        }

        if (children.find(s[index]) != children.end())
        {
            bool removeNext = children[s[index]]->remove(s, index + 1);
            if (removeNext)
                children.erase(s[index]);

            return cnt <= 0 && children.empty();
        }
    }

    int count(string s, int index = 0)
    {
        if (index == s.size())
            return cnt;

        if (children.find(s[index]) != children.end())
            return children[s[index]]->count(s, index + 1);
        else
            return 0;
    }

    int prefix(string s, int index = 0)
    {
        if (index == s.size())
            return s.size();

        if (children.find(s[index]) != children.end())
            return children[s[index]]->prefix(s, index + 1);
        else
            return index;
    }
};

int main()
{
    int op;
    string s;

    TrieNode trie;

    while(!f.eof() && f >> op >> s)
        switch (op)
        {
        case 0:
            trie.insert(s);
            break;
        case 1:
            trie.remove(s);
            break;
        case 2:
            g << trie.count(s) << '\n';
            break;
        case 3:
            g << trie.prefix(s) << '\n';
            break;
        }

    return 0;
}