题目链接: hdu 4287
题目大意: 手机打英文,先给出N个数字串表示按键的顺序
M个单词的词典,询问按下这些数字串分别会出现多少个词典中的单词
解题思路: 把单词转换成按键数字建成树
最后一个数字结点w值记录次数
查询的时候根据数字遍历字典树
最后一个数字结点的w值既是答案
代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> #define MAX 50100 struct snode{ int w; int next[10]; }Tree[MAX*10]; int Index; char ch[10],chnum[MAX][10]; int Find(char ch3) //字母对应手机的按键 { if(ch3=='a'||ch3=='b'||ch3=='c') return 2; else if(ch3=='d'||ch3=='e'||ch3=='f') return 3; else if(ch3=='g'||ch3=='h'||ch3=='i') return 4; else if(ch3=='j'||ch3=='k'||ch3=='l') return 5; else if(ch3=='m'||ch3=='n'||ch3=='o') return 6; else if(ch3=='p'||ch3=='q'||ch3=='r'||ch3=='s') return 7; else if(ch3=='t'||ch3=='u'||ch3=='v') return 8; else return 9; } void Insert(int Tlen) //遍历建立树 { int i,S=0,child; for(i=1;i<=Tlen;i++) { child=Find(ch[i-1]); //把单词转换成数字 if(Tree[S].next[child]==0) { if(i==Tlen) Tree[Index].w++; Tree[S].next[child]=Index++; } else { if(i==Tlen) Tree[Tree[S].next[child]].w++; } S=Tree[S].next[child]; } } int Query(int k,int Tlen) //遍历查询 { int i,S=0,child; for(i=1;i<=Tlen;i++) { child=chnum[k][i-1]-'0'; if(Tree[S].next[child]!=0) { if(i==Tlen) return Tree[Tree[S].next[child]].w; S=Tree[S].next[child]; } else //不存在此结点则返回0 return 0; } } int main() { int n,m,t,i,j; scanf("%d",&t); while(t--) { Index=1; memset(Tree,0,sizeof(Tree)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) //建立字典树 { scanf("%s",chnum[i]); } for(i=1;i<=m;i++) { scanf("%s",ch); Insert(strlen(ch)); } for(i=1;i<=n;i++) //查询 { printf("%d\n",Query(i,strlen(chnum[i]))); } } return 0; }