随笔：152 文章：0 评论：129 引用：0
Headacher
学习笔记，从一点一滴做起。
C++博客
首页
发新随笔
发新文章
联系
聚合
管理
PKU POJ 2001 Shortest Prefixes
Trie简单应用
CODE
#include
<
iostream
>
using
namespace
std;
struct
node{
node
*
child[
26
];
int
count;
}
*
root;
char
c[
1010
][
22
];
int
len[
1010
];
char
temp[
22
];
int
n
=
0
;
void
trie(){
root
=
new
node();
for
(
int
i
=
0
;i
<
26
;i
++
) root
->
child[i]
=
NULL;
}
void
insert(
int
k){
node
*
r
=
root,
*
p;
for
(
int
i
=
0
;i
<
len[k];i
++
){
if
(r
->
child[c[k][i]
-
'
a
'
]
==
NULL){
p
=
new
node; p
->
count
=
0
;
for
(
int
j
=
0
;j
<
26
;j
++
) p
->
child[j]
=
NULL;
r
->
child[c[k][i]
-
'
a
'
]
=
p;
}
r
=
r
->
child[c[k][i]
-
'
a
'
];
r
->
count
++
;
}
}
void
search(
int
k){
node
*
r
=
root;
for
(
int
i
=
0
;i
<
len[k];i
++
){
r
=
r
->
child[c[k][i]
-
'
a
'
];
temp[i]
=
c[k][i];
if
(r
->
count
==
1
){
temp[i
+
1
]
=
'
\0
'
;
return
;
}
}
temp[len[k]]
=
'
\0
'
;
}
int
main(){
trie();
while
(scanf(
"
%s
"
,c[n])
!=
EOF
&&
c[n][
0
]
!=
'
.
'
){
len[n]
=
strlen(c[n]);
insert(n);
n
++
;
}
for
(
int
i
=
0
;i
<
n;i
++
){
search(i);
printf(
"
%s %s\n
"
,c[i],temp);
}
system(
"
pause
"
);
return
0
;
}
发表于 2009-02-21 11:33
Headacher
阅读(817)
评论(1)
编辑
收藏
引用
评论
#
re: PKU POJ 2001 Shortest Prefixes
分舵发
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
CALENDER
<
2009年2月
>
日
一
二
三
四
五
六
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
1
2
3
4
5
6
7
公告
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔分类
ACM-ICPC(7)
(rss)
操作系统
(rss)
计算机组成与体系结构(2)
(rss)
数据结构和算法(34)
(rss)
数据库
(rss)
心情日记(20)
(rss)
随笔档案
2010年12月 (1)
2010年9月 (1)
2010年5月 (3)
2010年4月 (3)
2010年3月 (1)
2010年2月 (2)
2010年1月 (10)
2009年12月 (1)
2009年10月 (3)
2009年9月 (6)
2009年8月 (14)
2009年7月 (8)
2009年6月 (2)
2009年5月 (17)
2009年4月 (4)
2009年3月 (5)
2009年2月 (25)
2009年1月 (9)
2008年12月 (1)
2008年11月 (30)
2008年10月 (4)
2008年7月 (2)
ACM Teammates
Qinz
(rss)
SHFACM
(rss)
wudired
(rss)
The One
May
(rss)
搜索
积分与排名
积分 - 129214
排名 - 194
最新评论
1. re: POJ 1379 run away 模拟退火算法[未登录]
为何按你的代码交会RE呢?
--zhang
2. re: POJ 1947 树状dp[未登录]
评论内容较长,点击标题查看
--Sky
3. re: 独立集，覆盖集，支配集，最大团，最大匹配
评论内容较长,点击标题查看
--fly2best
4. re: HDU HDOJ 1004 Let the Balloon Rise 字典树[未登录]
尼玛 这就是个水题
--xxx
5. re: nuaa 1017 最大0,1子矩阵[未登录]
1 0 1 0 1
2 1 2 1 2
3 2 2 2 0
0 3 4 3 1
1 0 5 4 2 这个写错了吧
第三行第三列那个2应该为3才对
--hu
阅读排行榜
1. 独立集，覆盖集，支配集，最大团，最大匹配(7843)
2. 原码 补码 反码 移码(6342)
3. POJ 计算几何入门题目推荐（转）(5683)
4. POJ 1379 run away 模拟退火算法(4339)
5. 数据的浮点数表示(3871)
评论排行榜
1. POJ 1379 run away 模拟退火算法(12)
2. 我真是太笨了……(10)
3. PKU POJ 2186 Popular Cows 强连通分量(5)
4. 数论中的一些公式（转）(4)
5. HDU HDOJ 1005 Number Sequence(4)
Powered By:
博客园
模板提供
：
沪江博客
