链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1251
题目
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组 成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的 前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师 交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提 问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
分析与总结:
字典树的基本功能之一, 求前缀个数。
代码:
#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\n", count(root, str)); } return 0; }
查看本栏目更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索int
, 统计单词出现个数
, next
, 难题求解答
, root
, 单词
, 字典树
, 前缀
, str
, pat acm题
, 算法 ccf acm
, acm算法问题c语言hdu
, acm算法数据结构
, acm字符
网络流 acm 算法
统计难题、字典树、可持久化字典树、字典树算法、字典树模板,以便于您获取更多的相关知识。