class Trie {
    Trie *next[26];
    bool is_end;

public:
    Trie() : next(), is_end(false) {
    }

    Trie *helper(string word) {
        auto cur(this);
        for (auto c : word) {
            if (!cur)
                return nullptr;
            cur = cur->next[c - 'a'];
        }
        return cur;
    }

    void insert(string word) {
        auto cur = this;
        for (auto c : word) {
            c -= 'a';
            if (!cur->next[c])
                cur->next[c] = new Trie;
            cur = cur->next[c];
        }
        cur->is_end = true; // mark word
    }

    bool search(string word) {
        auto cur = helper(word);
        return cur ? cur->is_end : false;
    }


    bool startsWith(string prefix) {
        auto cur = helper(prefix);
        return cur != nullptr;
    }
};

class Solution {
    struct Trie {
        Trie* next[26];
        bool isEnd;
        Trie() : next(), isEnd() {}
        void add(string s) {
            auto cur(this);
            for (auto& c : s) {
                c -= 'a';
                if (!cur->next[c]) cur->next[c] = new Trie;
                cur = cur->next[c];
            }
            cur->isEnd = true;
        }
        int query(string s) { // 返回位置
            auto cur(this);
            int n = s.size();
            for (int i{}; i < n; ++i) {
                int c = s[i] - 'a';
                if (!cur->next[c]) break;
                if (cur->next[c]->isEnd) return i + 1;
                cur = cur->next[c];
            }
            return n;
        }
    };

public:
    string replaceWords(vector<string>& vs, string s) {
        Trie* root = new Trie;
        // 建树
        for (auto t : vs) root->add(t);
        stringstream ss(s);
        string ans{};
        while (ss) {
            string t;
            ss >> t;
            if (t.empty()) break;
            ans += t.substr(0, root->query(t));
            ans += ' ';
        }
        ans.pop_back();
        return ans;
    }
};

class MapSum {
    struct Trie {
        int val;
        Trie* next[26];
        Trie() : val(), next() {}
    };
    Trie* root;
    unordered_map<string, int> cnt;

public:
    MapSum() : root(new Trie), cnt() {}

    void insert(string key, int val) {
        int d{val};
        if (cnt.count(key)) d -= cnt[key];
        cnt[key] = val; // 更新
        auto cur(root);
        for (auto c : key) {
            c -= 'a';
            if (!cur->next[c]) cur->next[c] = new Trie;
            cur = cur->next[c];
            cur->val += d; // 前缀对应的 val 每次都更新
        }
    }

    int sum(string prefix) {
        auto cur(root);
        for (auto c : prefix) {
            c -= 'a';
            if (!cur->next[c]) return 0;
            cur = cur->next[c];
        }
        return cur->val;
    }
};