算法學(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)
評論(0)
編輯
收藏
引用
只有注冊用戶
登錄
后才能發(fā)表評論。
【推薦】100%開源!大型工業(yè)跨平臺軟件C++源碼提供,建模,組態(tài)!
網(wǎng)站導(dǎo)航:
博客園
IT新聞
BlogJava
博問
Chat2DB
管理
留言簿
(5)
給我留言
查看公開留言
查看私人留言
隨筆分類
動態(tài)規(guī)劃(13)
數(shù)據(jù)結(jié)構(gòu)(11)
搜索(9)
圖論(10)
未分類(6)
ACMers
搜索
積分與排名
積分 - 110471
排名 - 231
最新隨筆
1.?換個博客,重新開始學(xué)習(xí)。。。
2.?pku 1691 Painting A Board 狀態(tài)壓縮DP
3.?HDU 1255
4.?PKU 1151
5.?2009年ACM-ICPC亞洲區(qū)預(yù)選賽共設(shè)十五個賽區(qū)如下(按現(xiàn)場賽日期排序)
6.?acmer必看的26個對acm態(tài)度
7.?ZJU 3228 Searching the String ( AC 自動機 )
8.?Pku 3169 Layout
9.?Pku 1986 Distance Queries
10.?Pku 1276 Cash Machine
最新評論
1.?re: AVL樹的插入和刪除操作
評論內(nèi)容較長,點擊標(biāo)題查看
--jasonkent27@163.com
Powered by:
博客園
模板提供:
滬江博客
Copyright ©2025 Darren
香蕉99久久国产综合精品宅男自
|
久久久WWW成人免费精品
|
一本色道久久88加勒比—综合
|
久久国产色AV免费观看
|
青草影院天堂男人久久
|
亚洲国产成人久久综合野外
|
亚洲中文字幕无码一久久区
|
精品国产乱码久久久久久郑州公司
|
日本免费久久久久久久网站
|
精品伊人久久久
|
国产精品久久精品
|
无码人妻久久一区二区三区蜜桃
|
久久久国产精品亚洲一区
|
狠狠色综合久久久久尤物
|
久久99精品久久久大学生
|
色综合久久88色综合天天
|
久久亚洲AV成人无码
|
亚洲精品高清国产一久久
|
久久免费视频1
|
亚洲国产精品久久久久久
|
无码超乳爆乳中文字幕久久
|
久久久久香蕉视频
|
久久夜色精品国产亚洲
|
久久婷婷成人综合色综合
|
亚洲国产成人久久笫一页
|
久久久久久亚洲精品无码
|
亚洲国产精品久久久久婷婷老年
|
久久婷婷五月综合国产尤物app
|
国产精品美女久久福利网站
|
久久国产精品一区
|
国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲
|
亚洲va国产va天堂va久久
|
欧美久久亚洲精品
|
久久99亚洲综合精品首页
|
欧美精品一区二区精品久久
|
国产精品一区二区久久国产
|
久久久久久久精品成人热色戒
|
久久99九九国产免费看小说
|
老司机午夜网站国内精品久久久久久久久
|
久久久久高潮综合影院
|
久久人人爽人人爽人人爽
|