建立一个字典树，先存入单词，再查找单词，最后输出具有该前缀的单词数量。
#include<cstdio>
#include<cstdlib>
struct node
{
int cnt;
int next[26];
} T[10000010];
int t=0;
char str[20];
void Insert(char *s)
{
int i=0, p=0, temp;
while(s[i])
{
temp=s[i]-'a';
if(T[p].next[temp]==0)
{
t++;
T[p].next[temp]=t;
}
p=T[p].next[temp];
T[p].cnt++;
i++;
}
}
void Query(char *s)
{
int i=0, p=0, temp;
while(s[i])
{
temp=s[i]-'a';
if(T[p].next[temp]==0)
{
printf("0\n");
return ;
}
p=T[p].next[temp];
i++;
}
printf("%d\n",T[p].cnt);
return ;
}
int main()
{
int m, n;
scanf("%d", &n);
getchar();
while(n--)
{
gets(str);
Insert(str);
}
scanf("%d", &m);
getchar();
while(m--)
{
gets(str);
Query(str);
}
return 0;
}
核心代码：
void Insert(char *s)
{
int i=0, p=0, temp;
while(s[i])
{
temp=s[i]-'a';
if(T[p].next[temp]==0)
{
t++;
T[p].next[temp]=t;
}
p=T[p].next[temp];
T[p].cnt++;
i++;
}
}
先判断是否存在该前缀，如果不存在，就构建新的枝叶。
查找一个就为该枝叶记一次数，表示到该枝叶的前缀个数
