算法题：HDU 1251 统计难题（字典树，统计前缀个数）

算法题：HDU 1251 统计难题（字典树，统计前缀个数）2014-03-17 csdn博客 shuangde800链接：

http://acm.hdu.edu.cn/showproblem.php？pid=1251

题目

Problem Description

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

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

Output

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

Sample Input

bananabandbeeabsoluteacmbabbandabc

Sample Output

分析与总结：

字典树的基本功能之一，求前缀个数。

代码：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int KIND = 26;const int MAXN = 150000;int cntNode;struct node{bool isword;int prefix;node *next[KIND];void init（）{isword=0;prefix=0;memset（next, 0, sizeof（next））;}}HEAP[MAXN];inline node* newNode（）{HEAP[cntNode].init（）;return &HEAP[cntNode++];}void insert（node* root, char *str）{for（char *p=str; *p; ++p）{int ch=*p-"a";if（root->next[ch]==NULL）{root->next[ch] = newNode（）;}root = root->next[ch];root->prefix++; }root->isword=true;}int count（node *root, char *str）{ // 返回前缀数量int sum=0;for（char *p=str; *p; ++p）{char ch=*p-"a";if（root->next[ch]==NULL） return 0;root=root->next[ch];}return root->prefix;}int main（）{char str[12];node *root = newNode（）;while（gets（str））{if（str[0]==0）break;insert（root, str）;}while（gets（str））{printf（"%d
", count（root, str））;}return 0;}