https://vjudge.net/problem/HDU-1251

标准的字典树模板题:

也注意一下输入方法:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = ;
struct node
{
int num;
node *next[maxn];
}; //字典树
class Tree{
public:
node *head;
//构造函数
Tree()
{
head = New();
}
//创建一个新节点
node* New()
{
node *p = new node();
for (int i = ; i < maxn; ++i)
{
p->next[i] = NULL;
}
p->num = ;
return p;
}
//插入一个字符串
void insert(char *str)
{
int len = strlen(str);
node *t, *p = head;
for (int i = ; i < len; ++i)
{
int c = str[i] - 'a';
if (p->next[c] == NULL)
{
t = New(); //创建新的节点
p->next[c] = t;
}
p = p->next[c];
p->num++;
}
}
int find(char *str)
{
node *p = head;
int len = strlen(str);
for (int i = ; i < len; ++i)
{
int c = str[i] - 'a';
if (p->next[c] == NULL)
return ; //不存在这样的字符串
p = p->next[c];
}
return p->num;
}
};
int main()
{
char s[];
Tree tree;
while (cin.getline(s, ))
{
if (strlen(s) == || strcmp(s, " ") == )break; //判断是是否为空行
tree.insert(s);
}
while (~scanf("%s", s))
{
printf("%d\n", tree.find(s));
}
}
04-29 03:18