Cod sursa(job #2489984)

Utilizator MaligMamaliga cu smantana Malig Data 9 noiembrie 2019 15:25:45
Problema Trie Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.88 kb
#include <bits/stdc++.h>

using namespace std;

#if 1
    #define pv(x) std::cerr<<#x<<" = "<<(x)<<"; ";std::cerr.flush()
    #define pn std::cerr<<std::endl
#else
    #define pv(x)
    #define pn
#endif

#ifdef INFOARENA
    ifstream in("trie.in");
    ofstream out("trie.out");
#else
    #define in cin
    #define out cout
#endif

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pld = pair<ld, ld>;
#define pb push_back
const double PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862;
const int inf_int = 1e9 + 5;
const ll inf_ll = 1e18 + 5;
const int NMax = 1e2 + 5;
const int dx[] = {-1,0,0,+1}, dy[] = {0,-1,+1,0};
const double EPS = 1e-8;

struct TrieNode {
    int val;
    int numSons = 0;
    TrieNode *nxt[26];
    TrieNode() {
        val = 0;
        for (int i = 0; i < 26; ++i) {
            nxt[i] = NULL;
        }
    }
} root;

void firstOp(TrieNode *node, const char *word, int curr, int wordLen, int add) {
    if (curr == wordLen) {
        node->val += add;
        return;
    }

    int idx = word[curr] - 'a';
    if (node->nxt[idx] == NULL) {
        node->nxt[idx] = new TrieNode();
        node->numSons += 1;
    }
    
    firstOp(node->nxt[idx], word, curr + 1, wordLen, add);
    TrieNode *nxt = node->nxt[idx];
    if (nxt->val + nxt->numSons == 0) {
        delete nxt;
        node->nxt[idx] = NULL;
        node->numSons -= 1;
    }
}

int thirdOp(TrieNode *node, const char *word, int curr, int wordLen) {
    if (curr == wordLen) {
        return node->val;
    }

    int idx = word[curr] - 'a';
    if (node->nxt[idx] == NULL) {
        return 0;
    }
    return thirdOp(node->nxt[idx], word, curr + 1, wordLen);
}

int prefixOf(TrieNode *node, const char *word, int curr, int wordLen) {
    if (curr == wordLen) {
        return wordLen;
    }

    int idx = word[curr] - 'a';
    if (node->nxt[idx] == NULL) {
        return curr;
    }
    return prefixOf(node->nxt[idx], word, curr + 1, wordLen);
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    
    int op;
    string word;
    in >> op;
    while (!in.fail()) {
        in >> word;

        // pv(op);pv(word);pn; ///

        switch (op) {
            case 0: {
                firstOp(&root, word.c_str(), 0, word.size(), +1);
                break;
            }
            case 1: {
                firstOp(&root, word.c_str(), 0, word.size(), -1);
                break;
            }
            case 2: {
                int cnt = thirdOp(&root, word.c_str(), 0, word.size());
                out << cnt << '\n';
                break;
            }
            case 3: {
                int len = prefixOf(&root, word.c_str(), 0, word.size());
                out << len << '\n';
                break;
            }
        }

        in >> op;
    }

    return 0;
}