hdu1251（Trie树）

传送门：统计难题

分析：Trie树入门题，随便写写练下手感，统计每个节点被多少单词经过就可以了。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define LL long long
#define N 500010
using namespace std;

char s[15];
struct Trie
{
    int cnt[N],child[N][27];
    int L,root;
    int newnode()
    {
        memset(child[L],0,sizeof(child[L]));
        return L++;
    }
    void init()
    {
        L=0;
        memset(cnt,0,sizeof(cnt));
        root=newnode();
    }
    void insert(char *s)
    {
        int now=root;
        for(int i=0;s[i];i++)
        {
            int id=s[i]-'a';
            if(!child[now][id])
                child[now][id]=newnode();
            now=child[now][id];
            cnt[now]++;
        }
    }
    int query(char *s)
    {
        int now=root;
        for(int i=0;s[i];i++)
        {
            int id=s[i]-'a';
            if(!child[now][id])return 0;
            now=child[now][id];
        }
        return cnt[now];
    }
}trie;
int main()
{
    trie.init();
    while(gets(s))
    {
        if(strlen(s)==0)break;
        trie.insert(s);
    }
    while(scanf("%s",s)==1)printf("%d
",trie.query(s));
}