字典树

struct TrieNode {
    TrieNode* next[26];
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = nullptr;
        }
    }
};
class Trie {
public:
    TrieNode* root = new TrieNode();
    void insert(string& s) {
        auto p = root;
        for (auto& c : s) {
            if (p->next[c - 'a'] == nullptr) {
                p->next[c - 'a'] = new TrieNode();
            }
            p = p->next[c - 'a'];
        }
    }
    int match_prefix(string& s) {
        auto p = root;
        int len = 0;
        for (auto& c : s) {
            if (p->next[c - 'a'] == nullptr) {
                return len;
            }
            len++;
            p = p->next[c - 'a'];
        }
        return len;
    }
    bool search(string& s) {
        auto p = root;
        for (auto& c : s) {
            if (p->next[c - 'a'] == nullptr) {
                return false;
            }
            p = p->next[c - 'a'];
        }
        return true;
    }
};