Trie

#include <bits/stdc++.h>
using namespace std;

const int ALPHA = 26;

struct Trie {
    struct Node {
        int ch[ALPHA];
        int freq;
        bool isEnd;
    };

    vector<Node> t;

    Trie() { t.push_back({{}, 0, false}); }

    int newNode() { t.push_back({{}, 0, false}); return t.size() - 1; }

    void insert(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) t[cur].ch[idx] = newNode();
            cur = t[cur].ch[idx];
            t[cur].freq++;
        }
        t[cur].isEnd = true;
    }

    bool search(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return false;
            cur = t[cur].ch[idx];
        }
        return t[cur].isEnd;
    }

    bool startsWith(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return false;
            cur = t[cur].ch[idx];
        }
        return true;
    }

    void erase(const string& s) {
        if (!search(s)) return;
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            int nxt = t[cur].ch[idx];
            t[nxt].freq--;
            if (t[nxt].freq == 0) { t[cur].ch[idx] = 0; return; }
            cur = nxt;
        }
        t[cur].isEnd = false;
    }

    int countPrefix(const string& s) {
        int cur = 0;
        for (char c : s) {
            int idx = c - 'a';
            if (!t[cur].ch[idx]) return 0;
            cur = t[cur].ch[idx];
        }
        return t[cur].freq;
    }
};