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

gzwzm06

  C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
  1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks
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 
*= 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 , *= 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, 
00, 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)  編輯 收藏 引用 所屬分類: 字符串處理

評論

# re: Pku 2774--Long Long Message(后綴樹) 2011-05-15 13:51 dereky
求教大牛,那個Lt屬性是記錄什么的  回復  更多評論
  

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            中国av一区| 最新中文字幕亚洲| 亚洲第一区中文99精品| 欧美成人免费小视频| 欧美在线黄色| 欧美日韩国产亚洲一区| 久久免费国产| 国产精品视频久久久| 91久久久久久久久久久久久| 韩国av一区| 午夜在线电影亚洲一区| 亚洲影院在线| 欧美日韩中字| 亚洲精品乱码久久久久久蜜桃麻豆| 国内精品久久久久久久影视蜜臀 | 国产亚洲欧美日韩一区二区| 日韩视频一区二区在线观看 | 国产麻豆9l精品三级站| 亚洲理论电影网| 亚洲高清久久久| 久久久久9999亚洲精品| 久久久精品一区| 国产婷婷色一区二区三区在线| 一区二区三区日韩欧美精品| 一区二区三区日韩欧美| 欧美激情久久久| 亚洲免费播放| 亚洲午夜极品| 欧美午夜精品久久久久久人妖| 亚洲日韩成人| 99热这里只有成人精品国产| 免费在线看一区| 亚洲国产欧美日韩另类综合| 亚洲精品视频在线观看网站 | 久久激情视频久久| 久久精品女人的天堂av| 国产日韩欧美在线视频观看| 亚洲一区二区三区在线视频| 欧美影院午夜播放| 国产一区二区福利| 久久久久久欧美| 欧美成人精品激情在线观看| 精品成人乱色一区二区| 久久免费少妇高潮久久精品99| 免费看精品久久片| 亚洲黄色一区| 欧美日韩一区视频| 亚洲一区二区免费视频| 久久成人免费电影| 在线看日韩av| 欧美精品二区三区四区免费看视频| 亚洲日韩视频| 羞羞色国产精品| 国内成人精品视频| 欧美第十八页| 亚洲午夜av在线| 久热这里只精品99re8久| 亚洲肉体裸体xxxx137| 欧美视频一区二区| 欧美在线看片| 亚洲国产精品999| 欧美呦呦网站| 亚洲日本欧美天堂| 国产伦精品一区| 欧美va天堂| 亚洲欧美日韩国产成人| 欧美福利电影网| 亚洲欧美综合v| 亚洲黄色性网站| 国产麻豆91精品| 欧美精品久久一区| 午夜久久一区| 亚洲精品乱码视频| 久久久久国产一区二区三区四区 | 欧美成人午夜激情视频| 在线中文字幕日韩| 激情综合网激情| 国产精品久久久久久久久久久久 | 国产精品区二区三区日本| 久久永久免费| 香港成人在线视频| 亚洲精品123区| 久久免费少妇高潮久久精品99| 99视频精品全部免费在线| 国产一区二区三区四区在线观看| 欧美激情视频一区二区三区在线播放| 亚洲欧美日韩在线播放| 日韩视频在线永久播放| 裸体素人女欧美日韩| 欧美一区二区在线看| 一区二区欧美亚洲| 亚洲片国产一区一级在线观看| 国产日韩一区二区三区| 欧美视频你懂的| 欧美福利视频一区| 久久夜色精品一区| 亚久久调教视频| 亚洲欧美日韩国产中文在线| 一本色道久久88综合亚洲精品ⅰ| 亚洲二区在线| 欧美大胆人体视频| 美女网站久久| 久久国产精彩视频| 欧美亚洲在线| 亚洲一区二区高清| 亚洲午夜极品| 一区二区三区av| 宅男噜噜噜66一区二区66| 亚洲精品午夜| 日韩一级二级三级| 日韩视频免费观看高清完整版| 亚洲精品黄色| 日韩午夜av在线| 99国产精品久久久久老师| 亚洲人永久免费| av成人免费在线观看| 日韩午夜激情| 亚洲一区二区av电影| 亚洲一区二区三区中文字幕| 亚洲一级特黄| 欧美在线一级视频| 久久久99久久精品女同性| 久久琪琪电影院| 欧美xxx成人| 亚洲欧洲一区二区在线播放| 亚洲国产人成综合网站| 日韩视频在线观看| 亚洲无限av看| 欧美在线亚洲综合一区| 久久久国产91| 欧美韩国日本一区| 欧美视频在线播放| 国产一区二区按摩在线观看| 精品成人免费| 一区二区久久久久| 欧美一区2区视频在线观看| 久久精品国亚洲| 女人色偷偷aa久久天堂| 亚洲激情亚洲| 亚洲综合视频网| 久久综合激情| 欧美日韩精品是欧美日韩精品| 国产精品夜夜夜一区二区三区尤| 国产亚洲精品美女| 亚洲日本欧美天堂| 亚洲欧美日韩国产成人| 看片网站欧美日韩| 亚洲精品久久久久久久久久久久久 | 久久色在线播放| 欧美屁股在线| 国产在线欧美| 日韩视频在线一区二区三区| 久久riav二区三区| 亚洲国产日韩美| 欧美亚洲视频一区二区| 欧美精品三级| 国产夜色精品一区二区av| 99精品视频一区二区三区| 欧美一区二区三区婷婷月色 | 久久久久久网址| 欧美视频在线免费| 在线欧美影院| 久久不射网站| 日韩一级网站| 免费日韩精品中文字幕视频在线| 国产精品免费视频xxxx| 日韩亚洲欧美中文三级| 久久久久久**毛片大全| 一区二区三区四区五区精品视频| 久久久久久久999精品视频| 国产精品久久久久久五月尺| 亚洲国产另类精品专区| 久久久久国产一区二区| 亚洲深夜av| 欧美日韩国产综合在线| 亚洲国产福利在线| 久久久久久夜| 亚洲欧美国产77777| 欧美视频一区二区| 日韩一二三区视频| 亚洲高清资源| 久久人人爽人人爽| 激情一区二区三区| 久久精品在线视频| 亚洲综合日韩中文字幕v在线| 欧美国产精品人人做人人爱| **性色生活片久久毛片| 久久久精品免费视频| 午夜精品久久久久久久蜜桃app | 99视频+国产日韩欧美| 欧美国产一区二区| 久久亚洲电影| 樱花yy私人影院亚洲| 久久久久国内| 久久久久国色av免费看影院| 国内精品99| 乱人伦精品视频在线观看| 久久久久综合一区二区三区| 在线播放视频一区| 欧美91福利在线观看|