久久99精品久久久久久野外,久久九九精品99国产精品,久久久久国产

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

只有注冊用戶登錄后才能發表評論。
【推薦】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 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論

評論