字典树（前缀树）例题 HDU 1251

题目点这里直达

题意很明确，就是字典树的裸题。

该数据结构的典型应用是统计，排序和保存大量的字符串（但不仅限于字符串）

资料 1：OI Wiki
资料 2 ：http://ddrv.cn/a/44982
代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=500001;
struct trie
{
    int nex[maxn][26], cnt; //nex[i][j]表示编号为i的节点的第j个孩子的编号；j是按照字符序存储的，i是编号
    bool exist[maxn];         // 该结点结尾的字符串是否存在
    int val[maxn];   //val[i]记录编号为i的节点信息
    void insert(char *s, int l) // 插入字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c])
                nex[p][c] = ++cnt; // 如果没有，就添加结点
            p = nex[p][c];
            ++val[p]; // 本题的核心,标记每一种前缀出现了几次
        }
        exist[p] = 1;
    }
    bool find(char *s, int l) // 查找字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c])
                return 0;
            p = nex[p][c];
        }
        return exist[p];
    }
    int query(char *s,int len)
    {
        int p=0;
        for(int i=0 ;i<len;i++)
        {
            int c=s[i]-'a';
            if(!nex[p][c])
                return 0;
            p=nex[p][c];
        }
        return val[p];
    }
};
trie a;
int main()
{
    
    char str[120];
    // scanf("%s",str);
   while (cin.getline(str,12), str[0])
    {
        int len = strlen(str);
        a.insert(str, len);
    }
    // puts("gg");
    // scanf("%s",str);
    while (scanf("%s", str) != EOF)
    {
        int len = strlen(str);
        // printf("%d\n",a.find(str,len));
        printf("%d\n",a.query(str,len));
    }
    return 0;
}