简单字典树
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[5100][10];
struct tree
{
struct tree *next[10];
int num;//记录以此节点结尾的字符串的个数
}*root;
void insert(char str[])//建字典树
{
int len=strlen(str);
tree *p=root,*q;
for(int i=0;i<len;i++)
{
int id=str[i]-'0';
if(p->next[id]==NULL)
{
q=(struct tree *)malloc(sizeof(tree));
for(int j=0;j<10;j++)
q->next[j]=NULL;
q->num=0;
p->next[id]=q;
p=p->next[id];
}
else
{
p=p->next[id];
}
}
p->num++;
}
int find(char str[])//查找字符串
{
int len=strlen(str);
struct tree *p=root;
for(int i=0;i<len;i++)
{
int id=str[i]-'0';
if(p->next[id]==NULL)return 0;
else p=p->next[id];
}
return p->num;
}
int main()
{
int i,m,n,t;
char ch[10];
scanf("%d",&t);
while(t--)
{
root=(struct tree *)malloc(sizeof(tree));
for(i=0;i<10;i++)
root->next[i]=NULL;
root->num=0;
scanf("%d%d",&n,&m);getchar();
for(i=0;i<n;i++)
gets(s[i]);
for(i=0;i<m;i++)
{
gets(ch);
for(int j=0;ch[j]!='\0';j++)
{
int a=ch[j]-'a';
if(a>=0&&a<3)ch[j]='2';
else if(a>2&&a<6)ch[j]='3';
else if(a>5&&a<9)ch[j]='4';
else if(a>8&&a<12)ch[j]='5';
else if(a>11&&a<15)ch[j]='6';
else if(a>14&&a<19)ch[j]='7';
else if(a>18&&a<22)ch[j]='8';
else if(a>21&&a<26)ch[j]='9';
}
insert(ch);
}
for(i=0;i<n;i++)
printf("%d\n",find(s[i]));
}
return 0;
}