[HDU][1251][字典树] 统计难题

题目大意：

Ignatius最近遇到一个难题，老师交给他很多单词（只有小写字母组成，不会有重复的单词出现），现在老师要他统计出以某个字符串为前缀的单词数量（单词本身也是自己的前缀）。

思路：

字典树模板题。

代码：

#include
#include
using namespace std;
struct trie
//利用结构体来封装字典树的节点。
{
    trie* next[26];
    int num;
    trie()
    //构造函数。
    {
        for(int i=0;i<26;i++)
            next[i]=NULL;
        num=0;
    }
}root;
void insert(char* s)
//将字符串s所表示的单词插入到字典树中。
{
    trie *p=&root;
    for(int i=0;s[i]!='\0';i++)
    {
        if(p->next[s[i]-'a']==NULL)
            p->next[s[i]-'a']=new trie;
        p=p->next[s[i]-'a'];
        p->num++;
    }
}
int find(char *s)
//返回值是以s为前缀的单词的数量。
{
    trie *p=&root;
    for(int i=0;s[i]!='\0';i++)
        if(p->next[s[i]-'a']==NULL)
            return 0;
        else
            p=p->next[s[i]-'a'];
    return p->num;
}
int main()
{
    char str[11];
    while(gets(str)&&str[0]!='\0')
        insert(str);
    while(~scanf("%s",str))
        printf("%d\n",find(str));
}