字典树

概念：Trie 将字符串的公共前缀共享在同一路径上。根到结点的边依次表示字符，结点的结束标记表示一个完整单词。

关键步骤

插入时逐字符沿对应儿子移动，缺失则新建；查询后检查是否到达结束标记。仅含小写字母时可用固定 26 分支数组。

struct Node{ int ch[26]{}; bool end=false; } tr[100005]; int tot=0;
void insert(const string& s){
    int p=0;
    for(char c:s){ int k=c-'a'; if(!tr[p].ch[k]) tr[p].ch[k]=++tot; p=tr[p].ch[k]; }
    tr[p].end=true;
}

复杂度

插入、查找和前缀判断均为 O(L)，L 是字符串长度。空间 O(字符总数 × 字符集大小)；字符集大或稀疏时可改用映射存儿子。