gzwzm06
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
<
2024年11月
>
日
一
二
三
四
五
六
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
29
30
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(3)
给我留言
查看公开留言
查看私人留言
随笔档案
2009年5月 (1)
文章分类
DP(12)
(rss)
Hash应用(4)
(rss)
几何(1)
(rss)
模拟题(2)
(rss)
数据结构(12)
(rss)
数学(2)
(rss)
搜索(2)
(rss)
图论(7)
(rss)
与Tree相关的题(2)
(rss)
字符串处理(8)
(rss)
文章档案
2009年5月 (8)
2009年4月 (5)
2009年3月 (14)
2008年11月 (20)
2008年10月 (5)
搜索
最新评论
1. re: Pku 2774--Long Long Message(后缀树)
求教大牛,那个Lt属性是记录什么的
--dereky
2. re: POJ 2481(树状数组)
@gzwzm06
哦,实在是不好意思,确实是那个地方,现在过了,谢谢了啊。
--Klion
3. re: POJ 2481(树状数组)
你再检查下,cc[j].m_e == cc[j].m_e这个条件肯定是真的,没有意义吧
--gzwzm06
4. re: POJ 2481(树状数组)
@gzwzm06
两个相同一起比较也就是两个区间是一样的,起点和终点是相同的,和您的第80行比较的应该是一样的吧?
--Klion
5. re: POJ 2481(树状数组)
评论内容较长,点击标题查看
--gzwzm06
Pku 2774--Long Long Message(后缀树)
Memory:
74320K
Time:
797MS
Language:
C++
Result:
Accepted
#include
<
stdio.h
>
#include
<
string
>
using
namespace
std ;
const
int
MAXN
=
200000
;
const
int
APSIZE
=
30
;
struct
SuffixTreeNode
{
SuffixTreeNode
*
descendants[APSIZE] ;
int
m_left[APSIZE], m_right[APSIZE] ;
SuffixTreeNode
*
suffixLink ;
SuffixTreeNode()
{
for
(
int
i
=
0
; i
<
APSIZE ;
++
i )
{
m_left[i]
=
-
1
;
}
}
}
;
SuffixTreeNode g_STNode[MAXN] ;
int
g_Level
=
0
;
SuffixTreeNode
*
NewSuffixTreeNode()
{
SuffixTreeNode
*
ptr
=
&
g_STNode[g_Level
++
] ;
return
ptr ;
}
SuffixTreeNode
*
root ;
struct
UkkonenSuffixTree
{
int
offset ;
int
Lt ;
string
T ;
bool
endPoint ;
UkkonenSuffixTree(
int
from)
{
Lt
=
1
;
offset
=
from ;
}
SuffixTreeNode
*
TestAndSplit( SuffixTreeNode
*
p,
int
i )
{
int
Rt
=
i
-
1
;
if
( Lt
<=
Rt )
{
int
pos
=
T.at(Lt)
-
offset ;
SuffixTreeNode
*
pp
=
p
->
descendants[pos] ;
int
lt
=
p
->
m_left[pos] ;
int
rt
=
p
->
m_right[pos] ;
if
( T.at(i)
==
T.at( lt
+
Rt
-
Lt
+
1
) )
{
endPoint
=
true
;
return
p ;
}
else
{
pos
=
T.at(lt)
-
offset ;
SuffixTreeNode
*
r
=
p
->
descendants[pos]
=
NewSuffixTreeNode() ;
p
->
m_right[pos]
=
lt
+
Rt
-
Lt ;
pos
=
T.at(lt
+
Rt
-
Lt
+
1
)
-
offset ;
r
->
descendants[pos]
=
pp ;
r
->
m_left[pos]
=
lt
+
Rt
-
Lt
+
1
;
r
->
m_right[pos]
=
rt ;
endPoint
=
false
;
return
r ;
}
}
else
if
( p
->
m_left[T.at(i)
-
offset]
==
-
1
)
{
endPoint
=
false
;
}
else
endPoint
=
true
;
return
p ;
}
SuffixTreeNode
*
FindCanonicalNode( SuffixTreeNode
*
p,
int
Rt )
{
if
( Rt
>=
Lt )
{
int
pos
=
T.at(Lt)
-
offset ;
SuffixTreeNode
*
pp
=
p
->
descendants[pos] ;
int
lt
=
p
->
m_left[pos] ;
int
rt
=
p
->
m_right[pos] ;
while
( rt
-
lt
<=
Rt
-
Lt )
{
Lt
=
Lt
+
rt
-
lt
+
1
;
p
=
pp ;
if
( Lt
<=
Rt )
{
pos
=
T.at(Lt)
-
offset ;
pp
=
p
->
descendants[pos] ;
lt
=
p
->
m_left[pos] ;
rt
=
p
->
m_right[pos] ;
if
( p
==
root )
pp
=
root ;
}
}
}
return
p ;
}
SuffixTreeNode
*
Update( SuffixTreeNode
*
p,
int
i )
{
SuffixTreeNode
*
prev
=
NULL ,
*
r
=
TestAndSplit( p, i ) ;
while
(
!
endPoint )
{
int
pos
=
T.at(i)
-
offset ;
r
->
m_left[pos]
=
i ;
r
->
m_right[pos]
=
T.length()
-
1
;
if
( prev
!=
NULL )
prev
->
suffixLink
=
r ;
prev
=
r ;
if
( p
==
root )
Lt
++
;
else
p
=
p
->
suffixLink ;
p
=
FindCanonicalNode( p, i
-
1
) ;
r
=
TestAndSplit( p, i ) ;
}
if
( prev
!=
NULL )
prev
->
suffixLink
=
p ;
return
p ;
}
void
Run(
string
text )
{
T
=
text ;
int
n
=
T.length() , pos
=
T.at(
0
)
-
offset ;
root
=
NewSuffixTreeNode() ;
root
->
suffixLink
=
root ;
root
->
m_left[pos]
=
0
;
root
->
m_right[pos]
=
n
-
1
;
SuffixTreeNode
*
canonicalNodeAP
=
root ,
*
canonicalNodeEP ;
for
(
int
i
=
1
; i
<
n ;
++
i )
{
canonicalNodeEP
=
Update( canonicalNodeAP, i ) ;
canonicalNodeAP
=
FindCanonicalNode( canonicalNodeEP, i ) ;
}
}
}
;
int
length
=
0
, s1length
=
0
;
void
TraverseTree(SuffixTreeNode
*
p,
int
lt,
int
len,
bool
&
a,
bool
&
b )
{
bool
edge1
=
false
, edge2
=
false
;
for
(
int
i
=
0
; i
<
APSIZE ;
++
i )
{
if
( p
->
m_left[i]
!=
-
1
)
{
if
( p
->
descendants[i]
==
NULL )
{
if
( p
->
m_left[i]
<=
s1length )
a
=
edge1
=
true
;
else
b
=
edge2
=
true
;
}
else
{
TraverseTree( p
->
descendants[i], p
->
m_left[i],
len
+
(p
->
m_right[i]
-
p
->
m_left[i]
+
1
) , edge1, edge2 ) ;
if
( edge1 )
a
=
true
;
if
( edge2 )
b
=
true
;
}
if
( edge1
&&
edge2
&&
len
>
length )
{
length
=
len ;
}
}
}
}
int
FindLongest()
{
bool
edge1
=
false
, edge2
=
false
;
TraverseTree( root,
0
,
0
, edge1, edge2 ) ;
return
length ;
}
int
main()
{
char
s1[
100000
], s2[
100000
] ;
gets(s1) ;
gets(s2) ;
int
l1
=
strlen(s1), l2
=
strlen(s2) ;
s1[l1]
=
'
|
'
, s1[l1
+
1
]
=
'
\0
'
;
s2[l2]
=
'
}
'
, s2[l2
+
1
]
=
'
\0
'
;
strcat( s1, s2 ) ;
s1length
=
l1 ;;
UkkonenSuffixTree t(
'
a
'
) ;
t.Run(s1) ;
int
ans
=
FindLongest() ;
printf(
"
%d\n
"
, ans) ;
return
0
;
}
posted on 2008-11-08 14:15
巫
阅读(587)
评论(1)
编辑
收藏
引用
所属分类:
字符串处理
评论
#
re: Pku 2774--Long Long Message(后缀树)
2011-05-15 13:51
dereky
求教大牛,那个Lt属性是记录什么的
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
POJ 2408--Anagram Groups
Pku 3080--Blue Jeans(暴力枚举 + KMP)
Pku 3630--Phone List(Trie)
Pku 2503--Babelfish(Trie)
Pku 1816--Wild Words(Trie + DFS)
Pku 2513--Colored Sticks(Trie)
Pku 2774--Long Long Message(后缀数组)
Pku 2774--Long Long Message(后缀树)
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 巫