Hdu 1251-统计难题（字典树模板题）

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1251

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

分析：
读入单词直接插入即可，由于这里要查询的是以该前缀为起始的单词数量，所以在加单词的时候，不仅要在单词末尾加值，同时在路径上所有结点都应该价值，最后查询该单词的权值即可

代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[26];
    int val;
    Trie(){
        val = 0;
        for (int i = 0 ; i < 26 ; i ++)
            next[i] = NULL;
    }
};

void addword(char *str,Trie* node)
{
    if (node->next[str[0]-'a']==NULL)
    {
        node->next[str[0]-'a'] = new Trie;
        node = node->next[str[0]-'a'];
        node->val ++;
    }
    else
    {
        node = node->next[str[0]-'a'];
        node->val ++;
    }
    //printf("%c\t",*str);
    str++;
    if (*str)
        addword(str,node);
    else
        return;
}

int query(char *str ,Trie *node)
{
    //printf("%c\t",*str);
    if (node->next[*str-'a']==NULL)
        return 0;
    else
        node= node->next[*str-'a'];
    ++str;
    if (*str)
        return query(str,node);
    else
        return node->val;
}

char str[100];


int main()
{
    Trie *head = new Trie;
    char ch;
    int cnt ;
    while (ch=getchar())
    {
        cnt = 0;
        if (ch=='\n')
            break;

        while (ch!='\n')
        {
            str[cnt++] = ch;
            ch = getchar();
        }
        str[cnt]=0;
        addword(str,head);
    }

    while (~scanf("%s",str))
    {
        int ans = query(str,head);
        printf("%d\n",ans);
    }
    return 0;
}