题目链接: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 ;
}