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

            







            
	    
    


            

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

            




            






            

				

            



    
    







            
	   
	



久久精品99久久香蕉国产色戒
|
97久久精品午夜一区二区|
无码人妻精品一区二区三区久久久|
久久精品国产亚洲AV忘忧草18|
久久99久久99精品免视看动漫|
97精品伊人久久久大香线蕉|
一97日本道伊人久久综合影院|
久久精品毛片免费观看|
久久精品国产99久久丝袜|
久久精品亚洲日本波多野结衣
|
久久久久精品国产亚洲AV无码|
精品久久777|
国产成人综合久久精品红|
久久精品国产亚洲av高清漫画|
久久亚洲精品无码观看不卡|
丁香五月网久久综合|
一本色道久久综合亚洲精品|
久久久久久毛片免费看|
久久国产成人精品麻豆|
午夜天堂av天堂久久久|
亚洲美日韩Av中文字幕无码久久久妻妇|
国产一久久香蕉国产线看观看|
亚洲精品乱码久久久久66|
亚洲伊人久久成综合人影院
|
久久精品国产亚洲av影院|
亚洲国产综合久久天堂|
品成人欧美大片久久国产欧美...|
久久久免费精品re6|
综合人妻久久一区二区精品|
久久综合久久综合亚洲|
无码国内精品久久人妻麻豆按摩|
国产999精品久久久久久|
国产精品免费看久久久香蕉|
人妻无码中文久久久久专区
|
亚洲精品无码久久久久去q|
久久久久黑人强伦姧人妻|
国产AV影片久久久久久|
99久久精品国产综合一区|
99久久精品免费|
国产免费久久久久久无码|
国产伊人久久|