必须用string_view避免拷贝,TrieNode用std::array存储子节点并禁用拷贝操作,insert时通过sv[i]-'a'索引分支且需断言字符范围。

要在C++中实现毫秒级响应的前缀树(Trie)搜索,必须避开每次插入/查询都拷贝字符串的开销,同时压缩内存占用以提升缓存命中率——【string_view仅保存指针和长度,不持有所有权,是避免拷贝的关键】,而字典压缩需在构建阶段完成,不能拖慢在线查询。
定义轻量级TrieNode结构
用std::array<:unique_ptr>, 26>替代std::map
声明TrieNode时禁用拷贝构造与赋值:TrieNode(const TrieNode&) = delete; TrieNode& operator=(const TrieNode&) = delete;否则shared_ptr或unique_ptr语义易出错。
这一步操作起来很简单,直接把文件拖进去就行。
立即学习“C++免费学习笔记(深入)”;
用string_view构建Trie,禁止隐式转换
构造函数接收const std::vector<:string>&字典,但内部遍历转为std::vector<:string_view>视图数组——【必须显式构造string_view,禁止让编译器自动从const char*推导,否则临时字符串析构后view悬空】。
逐个调用insert(std::string_view sv)方法:从根节点出发,对sv[i] - 'a'取下标,若对应子节点为空则new TrieNode,继续向下;到达末尾时置is_end = true。
注意:只支持小写a-z,其他字符会越界访问array——上线前务必加assert(sv[i] >= 'a' && sv[i]
实现前缀匹配与字典压缩融合
方法一:构建后执行一次DFS遍历,合并所有“单路延伸且非终结”的节点链为压缩边——例如路径 a→b→c→d(仅d为end)可压成一条边"abcd",子节点挂d之后的分支(如有)。
方法二:在insert过程中动态压缩——每插入一个词,检查其路径上是否存在可合并的单子节点链,但会显著增加插入复杂度,不适合高频更新场景。
方法三:离线压缩(推荐):构建完整Trie后,调用compress()函数,用栈模拟DFS,对每个节点判断是否满足:子节点数==1 && is_end==false → 合并当前字符到子节点的压缩label,并将子节点的子树整体上移。这一步必须后序遍历,否则父节点被删后子树丢失。
高性能prefix_search实现
第一步:输入std::string_view prefix,从根节点开始遍历。
第二步:对prefix每个字符c,计算idx = c - 'a';若当前节点children[idx]为空,立即返回空vector。
第三步:到达prefix末尾后,从此节点出发BFS收集所有is_end == true的路径——但不用拼接完整字符串,而是回溯记录每条路径的压缩label序列,最后用std::string构造结果。
关键优化:BFS队列中存的是{current_node, current_string_length},而非完整string或string_view;拼接动作只在叶子节点触发,避免中间节点反复拷贝。



















