一道简单的Trie树应用，没什么难的
主要是理解一下建树过程和查找过程
/* 经典trie树（字典树）问题 给出n个字符串后 询问m次 每次询问输入一个字符串str 输出为原来n个字符串里面有多少个是以str作为前缀的字符串 */ #include<iostream> #include<cstdio> using namespace std; struct node { int num; node *chi[26]; node() { num=0; for(int i=0; i<26; i++) chi[i]=NULL; } }*root; void InsertTrie(char str[])//trie树插入 { node *temp=root;//每个单词创建一棵trie树，根节点没有赋值 for(int i=0; str[i]; i++) { int j=str[i]-'a'; if(temp->chi[j]==NULL)//如果temp节点没有chi[j]子节点 temp->chi[j]=new node;//创建一个跟node同类型的子节点 temp=temp->chi[j];//，每个子节点向上移一层 temp->num++; } } int SearchTrie(char str[])//trie树查找 { node *temp=root; for(int i=0; str[i]; i++) { int j=str[i]-'a'; if(temp->chi[j]==NULL)return 0; temp=temp->chi[j]; } return temp->num; } int main() { int n; char str[15]; while(~scanf("%d",&n)) { root=new node; while(n--) { scanf("%s",str); InsertTrie(str); } int m; scanf("%d",&m); while(m--) { scanf("%s",str); printf("%d\n",SearchTrie(str)); } } return 0; }