• <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>
            

    
            

            




            







												


        

            
	

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

            







            
	    
    


            

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

            




            






            

				

            



    
    







            
	   
	



久久久久综合网久久|
久久91亚洲人成电影网站|
国产精品久久网|
天堂久久天堂AV色综合|
久久人人爽人人爽人人av东京热|
国产精品免费久久久久久久久|
国产精品99久久精品|
国产精品一区二区久久精品|
久久99精品国产自在现线小黄鸭
|
九九热久久免费视频|
久久国产精品99久久久久久老狼|
久久久久久九九99精品|
国产亚洲欧美精品久久久|
国产精品18久久久久久vr|
99久久国产综合精品网成人影院|
久久精品国产只有精品66|
噜噜噜色噜噜噜久久|
久久精品国产亚洲av麻豆蜜芽|
亚洲午夜久久久久妓女影院|
久久综合给合久久国产免费|
久久久久亚洲AV片无码下载蜜桃|
国产亚洲精久久久久久无码AV|
国产成人精品久久亚洲高清不卡 |
久久九九久精品国产免费直播|
久久伊人色|
无码人妻精品一区二区三区久久|
久久精品无码午夜福利理论片|
久久线看观看精品香蕉国产|
久久久久综合中文字幕|
午夜人妻久久久久久久久|
91久久香蕉国产熟女线看|
亚洲综合熟女久久久30p|
99久久人人爽亚洲精品美女|
麻豆精品久久久久久久99蜜桃|
国产成人久久精品区一区二区|
久久久精品国产亚洲成人满18免费网站|
久久婷婷五月综合成人D啪|
99久久精品九九亚洲精品|
亚洲国产美女精品久久久久∴|
久久播电影网|
久久亚洲国产欧洲精品一|