gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2011年5月

>

日

一

二

三

四

五

六

24

25

26

27

28

29

30

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

31

1

2

3

4

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

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 巫閱讀(614) 評論(1) 編輯收藏引用所屬分類: 字符串處理

只有注冊用戶登錄后才能發表評論。


相關文章: 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 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論

評論