HDU 1251-统计难题（字典树-统计前缀串）

ゝ一世哀愁。 2022-08-21 13:47 166阅读 0赞

# 统计难题 #

**Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)  
Total Submission(s): 29895 Accepted Submission(s): 11668**

Problem Description

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

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.  
  
注意:本题只有一组测试数据,处理到文件结束.

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

Sample Input

banana
    band
    bee
    absolute
    acm
    
    ba
    b
    band
    abc

Sample Output

2
    3
    1
    0

Author

Ignatius.L  
  
一个可以套模板的字典树裸题，注意一个空行代表单词表的结束的输入结束判断就好。

/* 
    * Copyright (c) 2016, 烟台大学计算机与控制工程学院 
    * All rights reserved. 
    * 文件名称：tree.cpp 
    * 作    者：单昕昕 
    * 完成日期：2016年5月4日 
    * 版 本 号：v1.0 
    */  
    #include <cstdio>
    #include <iostream>
    using namespace std;
    struct Node
    {
        int num,next[27];//num是树的数目
    };
    
    Node a[1000005];
    int n,e;
    
    void Insert(char str[])
    {
        int i,p=1;
        for (i=0; str[i]; i++)
        {
            if (a[p].next[str[i]-'a']==0)//如果当前字母没有出现过
            {
                a[p].next[str[i]-'a']=++e;
                a[e].num=0;
            }
            p=a[p].next[str[i]-'a'];
            a[p].num++;
        }
    }
    
    int Search(char str[])//遍历输出
    {
        int i,p=1;
        for (i=0; str[i]; i++)
        {
            if (a[p].next[str[i]-'a']) p=a[p].next[str[i]-'a'];//如果存在当前字符串
            else return 0;//不存在直接判0
        }
        return a[p].num;
    }
    
    int main ()
    {
        char str[35];
        n=0;
        e=1;
        while(gets(str),*str)//或者写成&&str[0]
            Insert (str),n++;
        while(gets(str))
            cout<<Search(str)<<endl;
        return 0;
    }

如果一个一个建树就容易内存超限，比如下面这个：

#include <stdio.h>
    #include <iostream>
    using namespace std;
    #define MAXN 26
    typedef struct TrieNode
    {
        int nCount;  // 该节点前缀出现的次数
        struct TrieNode *next[MAXN]; //该节点的后续节点
    } TrieNode;
    TrieNode Memory[1000000]; //先分配好内存， malloc 较为费时
    int allocp = 0;
    
    TrieNode * createTrieNode()
    {//初始化一个节点。nCount计数为1， next都为null
        TrieNode * tmp = &Memory[allocp++];
        tmp->nCount = 1;
        for (int i = 0; i < MAXN; i++)
            tmp->next[i] = NULL;
        return tmp;
    }
    
    void insertTrie(TrieNode * * pRoot, char * str)
    {
        TrieNode * tmp = *pRoot;
        int i = 0, k;
        //一个一个的插入字符
        while (str[i])//插入整个字符串
        {
            k = str[i] - 'a'; //当前字符应该插入的位置
            if (tmp->next[k])//如果当前位置有当前字符
                tmp->next[k]->nCount++;//前缀计数++
            else//如果当前位置没有当前字符
                tmp->next[k] = createTrieNode();//初始化当前节点
            tmp = tmp->next[k];//以当前字符为新的节点位置
            i++; //移到下一个字符
        }
    
    }
    
    int searchTrie(TrieNode * root, char * str)
    {
        if (root == NULL)
            return 0;
        TrieNode * tmp = root;
        int i = 0, k;
        while (str[i])
        {
            k = str[i] - 'a';
            if (tmp->next[k]) tmp=tmp->next[k];
            else return 0;
            i++;
        }
        return tmp->nCount; //返回最后的那个字符所在节点的nCount
    }
    
    int main()
    {
        char s[35];
        TrieNode *Root = createTrieNode();
        while (gets(s) && s[0])
        {
            insertTrie(&Root, s);
        }
        while (gets(s)) //查询输入的字符串
        {
            printf("%d\n", searchTrie(Root, s));
        }
        return 0;
    }