统计难题

很久就看过这个题了，但不会~~~不会~~

题意：给出一张单词表，然后下面有若干查询，每次给出一个单词，问单词表中是否存在以这个单词为前缀的单词，输出数量。本身也是自身的前缀。只有一组数据！

思路：用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;

}

结束记得释放内存！虽然还有点没搞清~