【问题描述】
给出n个单词组成的字典（可能由相同的单词），请你完成下列任务：
任务1、把n个单词去重后按字典序由小到大后输出。
任务2、给出m个询问，每次询问一个单词是否在字典中存在，如果存在，输出该单词在字典中出现的次数。
【输入格式】
第一行为n和m。 接下来的n行，每行一个单词。 中间空一行。 在接下来的m行，每行一个单词，表示一个询问。
【输出格式】
开始的n行为任务1的输出结果。空一行后输出m行，每行一个整数，表示询问的结果（不存在，则输出0）。
【输入样例】
5 3 acd abc cba cba aab
cba abc aaa
【输出样例】
aab abc acd cba
2 1 0
【数据范围】
n,m<=50000 所有单词由大小写英文字母组成，长度不超过50
【来源】
Mr_He原创
如题，就是一道trie树的题。 trie树的定义如下： 1） 、Trie 树的根节表示字典的开始 2） 、每条边代表一个字符 3） 、从根节点出发，向下走到某节点过程中，经过的边代 表的字符连接起来构成一个字符串 4）、每个节点给定一个权值，表示是否是一个单词的结束 点或其他含义（成为单词节点）
储存方式就是一个数组（个人习惯用ch表示，同步线段树），然后查询的时候，直接跟着树走，能走到的单词就有，不能的就没有。
详细代码如下：（这里用的递归写法，其实大部分时候用的非递归写法）
#include<cstdlib> #include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn=50000*50+5; int m[maxn][52]={0},cnt=0,root=0,v[maxn]={0},n,mm; char s[55]; int r(char ch) { if(ch>='A'&&ch<='Z') return ch-'A'; if(ch>='a'&ch<='z') return ch-'a'+26; } void in(int &now,int i,char *ch)//加入单词（递归版，非递归版留个读者自行思考） { if(!now) now=++cnt; if(!ch[i]) { v[now]++; return; } int d=r(ch[i]); in(m[now][d],i+1,ch); } void init() { scanf("%d%d",&n,&mm); char ch[55]; for(int i=1;i<=n;i++) { scanf("%s",ch); in(root,0,ch); } } void work(int now,int i)//输出这棵树（以后一般用了检查代码） { if(v[now]) { s[i]=0; printf("%s\n",s); } for(int k=0;k<52;k++) if(m[now][k]) { s[i]= k<26? k+'A':k-26+'a'; work(m[now][k],i+1); } } int find(char *ch)//找单词 { int now=root; for(int i=0;ch[i];i++) { int d=r(ch[i]); if(!m[now][d]) return 0; now=m[now][d]; } return v[now]; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init(); work(root,0); printf("\n"); char ch[55]; int id; for(int i=1;i<=mm;i++) { scanf("%s",ch); printf("%d\n",find(ch)); } return 0; }