算法學(xué)習(xí)
C++ 及算法
C++博客
首頁
新隨筆
聯(lián)系
管理
HDU 2222 Keywords Search
#include
<
iostream
>
#include
<
queue
>
using
namespace
std;
struct
Trie
{
int
cnt;
Trie
*
next[
26
],
*
prefix;
}
Table[
500000
];
int
index
=
0
;
Trie
*
root;
char
str[
1000001
];
void
init()
{
index
=
0
;
root
=
&
Table[index];
memset( Table[
0
].next,
0
,
sizeof
(Table[
0
].next) );
Table[
0
].cnt
=
0
; Table[
0
].prefix
=
NULL;
}
void
insert(
char
*
s )
{
Trie
*
r
=
root;
while
(
*
s )
{
int
t
=
*
s
-
'
a
'
;
if
(
!
r
->
next[t] )
{
++
index;
memset( Table[index].next,
0
,
sizeof
(Table[index].next) );
Table[index].cnt
=
0
; Table[index].prefix
=
NULL;
r
->
next[t]
=
&
Table[index];
}
r
=
r
->
next[t]; s
++
;
}
r
->
cnt
++
;
}
void
get_prefix()
{
Trie
*
r
=
root;
queue
<
Trie
*>
q;
q.push( root ); root
->
prefix
=
NULL;
while
(
!
q.empty() )
{
Trie
*
father
=
q.front(); q.pop();
for
(
int
i
=
0
; i
<
26
;
++
i )
if
( father
->
next[i] )
{
Trie
*
tmp
=
father
->
prefix;
while
( tmp
&&
!
tmp
->
next[i] ) tmp
=
tmp
->
prefix;
if
(
!
tmp ) father
->
next[i]
->
prefix
=
root;
else
father
->
next[i]
->
prefix
=
tmp
->
next[i];
q.push( father
->
next[i] );
}
}
}
int
ac_run()
{
Trie
*
p
=
root;
int
ans
=
0
;
char
*
s
=
str;
while
(
*
s )
{
int
t
=
*
s
-
'
a
'
;
while
(
!
p
->
next[t]
&&
p
!=
root ) p
=
p
->
prefix;
p
=
p
->
next[t];
if
(
!
p ) p
=
root;
Trie
*
tp
=
p;
while
( tp
!=
root
&&
tp
->
cnt
!=
-
1
)
{
ans
+=
tp
->
cnt;
tp
->
cnt
=
-
1
;
tp
=
tp
->
prefix;}
s
++
;
}
return
ans;
}
int
main()
{
int
test;
scanf(
"
%d
"
,
&
test );
while
( test
--
)
{
int
n;
char
s[
55
];
scanf(
"
%d
"
,
&
n ); init(); getchar();
for
(
int
i
=
0
; i
<
n;
++
i )
{
gets(s); insert(s); }
gets(str); get_prefix();
printf(
"
%d\n
"
, ac_run() );
}
return
0
;
}
posted on 2009-04-15 14:17
Darren
閱讀(382)
評(píng)論(0)
編輯
收藏
引用
只有注冊(cè)用戶
登錄
后才能發(fā)表評(píng)論。
【推薦】100%開源!大型工業(yè)跨平臺(tái)軟件C++源碼提供,建模,組態(tài)!
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
留言簿
(5)
給我留言
查看公開留言
查看私人留言
隨筆分類
動(dòng)態(tài)規(guī)劃(13)
數(shù)據(jù)結(jié)構(gòu)(11)
搜索(9)
圖論(10)
未分類(6)
ACMers
搜索
積分與排名
積分 - 110595
排名 - 231
最新隨筆
1.?換個(gè)博客,重新開始學(xué)習(xí)。。。
2.?pku 1691 Painting A Board 狀態(tài)壓縮DP
3.?HDU 1255
4.?PKU 1151
5.?2009年ACM-ICPC亞洲區(qū)預(yù)選賽共設(shè)十五個(gè)賽區(qū)如下(按現(xiàn)場賽日期排序)
6.?acmer必看的26個(gè)對(duì)acm態(tài)度
7.?ZJU 3228 Searching the String ( AC 自動(dòng)機(jī) )
8.?Pku 3169 Layout
9.?Pku 1986 Distance Queries
10.?Pku 1276 Cash Machine
最新評(píng)論
1.?re: AVL樹的插入和刪除操作
評(píng)論內(nèi)容較長,點(diǎn)擊標(biāo)題查看
--jasonkent27@163.com
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 Darren
超级97碰碰碰碰久久久久最新
|
欧美日韩精品久久久久
|
久久亚洲日韩看片无码
|
久久精品国产欧美日韩99热
|
免费精品久久天干天干
|
粉嫩小泬无遮挡久久久久久
|
久久国产精品久久
|
午夜精品久久影院蜜桃
|
青青草国产精品久久
|
伊人久久大香线焦AV综合影院
|
99久久99久久精品国产片果冻
|
国产69精品久久久久观看软件
|
久久久91精品国产一区二区三区
|
亚洲国产高清精品线久久
|
国产情侣久久久久aⅴ免费
|
精品久久久久久无码国产
|
久久久久AV综合网成人
|
久久受www免费人成_看片中文
|
久久久精品国产sm调教网站
|
久久综合亚洲色HEZYO社区
|
久久99热这里只有精品国产
|
99久久国产综合精品麻豆
|
亚洲AV无码1区2区久久
|
精品国产乱码久久久久软件
|
色播久久人人爽人人爽人人片AV
|
国产精品九九久久免费视频
|
久久精品国产亚洲av水果派
|
精品一久久香蕉国产线看播放
|
国产精品久久国产精麻豆99网站
|
久久久久久毛片免费播放
|
久久人人爽人人爽人人AV东京热
|
久久综合香蕉国产蜜臀AV
|
人人狠狠综合久久亚洲婷婷
|
国内精品久久国产大陆
|
亚洲欧美国产精品专区久久
|
久久91精品国产91久
|
成人免费网站久久久
|
一本久久a久久精品综合香蕉
|
亚洲精品无码久久久久去q
|
国产精品一区二区久久精品涩爱
|
A级毛片无码久久精品免费
|