Cod sursa(job #2691080)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 26 decembrie 2020 22:58:28
Problema Trie Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>
using namespace std;

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

class Trie {
  private:
    struct Node {
        int cnt = 0;
        int lvs = 0;
        int next[26] = {};
    };
    vector<Node> trie{1};

  public:
    void insert(const string& str) {
        int node = 0;
        for (char chr : str) {
            trie[node].lvs++;
            if (!trie[node].next[chr - 'a']) {
                trie[node].next[chr - 'a'] = trie.size();
                trie.emplace_back();
            }
            node = trie[node].next[chr - 'a'];
        }
        trie[node].cnt++;
        trie[node].lvs++;
    }

    void erase(const string& str) {
        int node = 0;
        pair<int, int> last;
        for (int i = 0; i < (int) str.size(); i++) {
            if (trie[node].lvs > 1)
                last = make_pair(node, i);
            trie[node].lvs--;
            node = trie[node].next[str[i] - 'a'];
        }
        if (trie[node].lvs > 1)
            last = make_pair(node, str.size());
        trie[node].lvs--;
        if (last.second < (int) str.size())
            trie[last.first].next[str[last.second] - 'a'] = 0;
    }

    int count(const string& str) {
        int node = 0;
        for (char chr : str) {
            if (!trie[node].next[chr - 'a'])
                return 0;
            node = trie[node].next[chr - 'a'];
        }
        return trie[node].cnt;
    }

    int lcp(const string& str) {
        int node = 0, len = 0;
        for (char chr : str) {
            if (!trie[node].next[chr - 'a'])
                return len;
            node = trie[node].next[chr - 'a'];
            len++;
        }
        return len;
    }
};

int main() {
    Trie trie;
    int type; string str;
    while (fin >> type >> str)
        if (!type)
            trie.insert(str);
        else if (type == 1)
            trie.erase(str);
        else if (type == 2)
            fout << trie.count(str) << '\n';
        else
            fout << trie.lcp(str) << '\n';
    return 0;
}