统计难题
很久就看过这个题了，但不会~~~不会~~
题意：给出一张单词表，然后下面有若干查询，每次给出一个单词，问单词表中是否存在以这个单词为前缀的单词，输出数量。本身也是自身的前缀。只有一组数据！
思路：用gets或输入字符都行。如果输入字符可以用map存图，维护每个单词的所有前缀，直接查找就行。要么就用字典树建图，路径每经过一次就加1，如果是新节点直接附为1。查找时要注意是否存在查找单词的指针，不存在或者为空直接返回0，因为没有给其赋值。空间复杂度26^i，i为单词的长度，相当于26叉树。
struct Tree
{
int f;
Tree *next[N];
};
void insert(Tree *root,char *s)
{
if(root==NULL||*s=='\0') return ;
Tree *q=root;
while(*s!='\0')
{
if(q->next[*s-'a']==NULL)//节点不存在，建立新的节点
{
Tree *temp=new Tree;
for(int i=0;i<N;i++) temp->next[i]=0;
temp->f=1;
q->next[*s-'a']=temp;
q=q->next[*s-'a'];
}
else
{
q=q->next[*s-'a'];
q->f++;
}
s++;
}
}
int query(Tree *root,char *s)
{
Tree *q=root;
while(*s!='\0'&&q!=NULL)
{
q=q->next[*s-'a'];
s++;
}
if(q==NULL) return 0;
return q->f;
}
void del(Tree *root)
{
for(int i=0;i<N;i++)
if(root->next[i]!=NULL)
del(root->next[i]);
delete(root);
}
int main()
{
char s[10];
Tree *root=new Tree;
for(int i=0;i<N;i++) root->next[i]=NULL;
while(gets(s)&&s[0])
{
insert(root,s);
}
while(gets(s))
{
printf("%d\n",query(root,s));
}
del(root);
return 0;
}
结束记得释放内存！虽然还有点没搞清~