题意：统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
字典树 今天晚上刚学的。。算法无涯啊。好多东西都不知道。
/*
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0 */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct dirtree
{
struct dirtree *child[26];
int n;
};
struct dirtree *root;
void Insert(char*source)
{
int i,j,len;
len=strlen(source);
if(len==0)return ;
struct dirtree *current,*newnode;
current=root;
for(i=0;i<len;i++)
{
if(current->child[source[i]-'a']!=0)
{
current=current->child[source[i]-'a'];
current->n=current->n+1;
}
else
{
newnode=(struct dirtree*)malloc(sizeof(struct dirtree));
for(j=0;j<26;j++)
{
newnode->child[j]=0;
}
current->child[source[i]-'a']=newnode;
current=newnode;
current->n=1;
}
}
}
int Find(char *source)
{
struct dirtree *current;
int len=strlen(source);
if(len==0)return 0;
current=root;
for(int i=0;i<len;i++)
{
if(current->child[source[i]-'a']!=0)
current=current->child[source[i]-'a'];
else
return 0;
}
return current->n;
}
int main()
{
char temp[11];
int i,j;
root=(struct dirtree*)malloc(sizeof(struct dirtree));
for(i=0;i<26;i++)
root->child[i]=0;
root->n=2;
while(gets(temp),strcmp(temp,"")!=0)
Insert(temp);
while(scanf("%s",temp)!=EOF){
i=Find(temp);
printf("%d/n",i);
}
return 0;
}