hdoj 1251 统计难题(字典树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1251

思路分析:该问题要求求出以某个字符串为前缀的单词数目,通过使用字典树,在字典树中添加count记录通过该结点的单词数目即可;

查找时找到前缀的最后一个单词的结点的count值即为所求;

代码如下:

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; const int KIND = ;
const int MAX_N = ;
struct Node
{
Node *next[];
int count;
Node ()
{
count = ;
memset(next, , sizeof(next));
}
}; void InsertTrie(Node *root, char *str)
{
Node *p = root;
int i = , k = ; while (str[i])
{
k = str[i] - 'a';
if (!p->next[k])
p->next[k] = new Node();
p = p->next[k];
p->count++;
++i;
}
} int Find(Node *root, char *str)
{
int i = , k = ;
Node *p = root; while (str[i])
{
k = str[i] - 'a';
if (!p->next[k])
return ;
p = p->next[k];
++i;
}
return p->count;
} int main()
{
int ans = ;
char str[MAX_N];
Node *root = new Node(); while (gets(str) && strcmp(str,"") != )
InsertTrie(root, str);
while (gets(str))
{
ans = Find(root, str);
printf("%d\n", ans);
}
return ;
}
上一篇:[源码解析] PyTorch 分布式 Autograd (1) ---- 设计


下一篇:BZOJ 3156: 防御准备 斜率优化DP