http://acm.hdu.edu.cn/showproblem.php?pid=1251
通过这道题学习一下Trie字典树.
#include <iostream>
#include
<fstream>
#include
<vector>
#include
<
string
>
#include
<algorithm>
#include
<map>
#include
<stack>
#include
<cmath>
#include
<queue>
#include
<
set
>
#include
<list>
#include
<cctype>
#include
<stdio.h>
#include
<stdlib.h>
#include
<
string
.h>
#define
REP(i,j,k) for(int i = j ; i < k ; ++i)
#define
MAXV (1000)
#define
INF (0x6FFFFFFF)
#define
MAX 26
using
namespace
std;
typedef
struct
Trie
{
Trie
*
next[MAX];
int
v;
//
这里表示该字符前缀出现的次数
};
Trie
*
root;
void
Insert(
char
*
str)
{
Trie
*current =
root;
int
len=
strlen(str);
if
(len==
0
)
return
;
REP(i,
0
,len)
{
//
若节点存在，则直接访问下一个节点,并此前缀出现次数+1
if
(current->next[str[i]-
'
a
'
]!=
NULL)
{
current
=current->next[str[i]-
'
a
'
];
current
->v++
;
}
//
若节点不存在，则新建节点并初始化
else
{
current
->next[str[i]-
'
a
'
]=(Trie*)malloc(
sizeof
(Trie));
current
=current->next[str[i]-
'
a
'
];
REP(i,
0
,
26
) current->next[i]=
NULL;
current
->v=
1
;
}
}
}
int
Find(
char
*
str)
{
int
len=
strlen(str);
struct
Trie *current=
root;
if
(len==
0
)
return
0
;
REP(i,
0
,len)
{
//
如果关键词本字符存在,则访问下一个节点
if
(current->next[str[i]-
'
a
'
]!=
NULL)
current
=current->next[str[i]-
'
a
'
];
else
return
0
;
//
不存在直接返回0
}
return
current->v;
//
返回该前缀出现次数
}
void
Init()
{
root
=(Trie *)malloc(
sizeof
(Trie));
REP(i,
0
,
26
) root->next[i]=
NULL;
root
->v=
1
;
}
int
main()
{
Init();
char
str[
11
];
//
freopen("in.txt","r",stdin);
while
(gets(str)&&strcmp(str,
""
)!=
0
)
Insert(str);
char
tmp[
11
];
while
(~scanf(
"
%s
"
,tmp))
printf(
"
%d\n
"
,Find(tmp));
return
0
;
}
