\quad 这里实现一个通用的Trie树模板，支持单词插入，查询某个单词出现次数和打印输出所有以某个字符串为前缀的所有字符串这三个功能。程序如下：
#include <iostream> #include <map> using namespace std; struct Node { char c; int cnt; // 以该节点为结尾的单词数目 map<char, Node *> child; Node(char c) { this->c = c; this->cnt = 0; child.clear(); } }; Node *root; // 往Trie树中插入一个单词 void insert(string &word) { Node *p = root; for(char c: word) { if(p->child.count(c) == 0) { Node *t = new Node(c); p->child[c] = t; } p = p->child[c]; } p->cnt ++ ; } // 查询一个单词出现次数 int query(string &word) { Node *p = root; for(char c: word) { if(p->child.count(c) == 0) return 0; p = p->child[c]; } return p->cnt; } void dfs(Node *node, string prefix) { string s = prefix; if(node->cnt != 0) cout << s << endl; for(auto &[c, t]: node->child) { s += c; dfs(t, s); } } // 找到以prefix为前缀的所有单词 void getPrefixWords(string prefix) { Node *p = root; for(char c: prefix) { if(p->child.count(c) == 0) return; p = p->child[c]; } dfs(p, prefix); } int main() { root = new Node('#'); // 初始化根节点 int n; cin >> n; while(n -- ) { char op; cin >> op; string s; cin >> s; if(op == 'I') insert(s); else cout << query(s) << endl; } getPrefixWords("a"); return 0; }