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

            







            
	    
    


            

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

            




            






            

				

            



    
    







            
	   
	



亚洲国产欧美国产综合久久|
日本亚洲色大成网站WWW久久|
久久久WWW免费人成精品|
久久99精品久久久久久水蜜桃|
久久996热精品xxxx|
久久综合一区二区无码|
亚洲国产精品无码久久|
欧美激情精品久久久久|
久久人人爽人人爽人人片av麻烦|
精品乱码久久久久久久|
色悠久久久久久久综合网|
区久久AAA片69亚洲|
久久久久无码国产精品不卡|
奇米影视7777久久精品|
午夜久久久久久禁播电影|
久久99热国产这有精品|
久久久久久久亚洲Av无码|
亚洲中文字幕无码久久2017|
久久久久久久久波多野高潮|
久久免费国产精品一区二区|
伊人久久大香线蕉综合热线|
久久精品国产99久久丝袜|
久久精品人成免费|
中文字幕久久波多野结衣av|
国产综合免费精品久久久|
久久国产高清字幕中文|
性高湖久久久久久久久|
久久亚洲国产精品成人AV秋霞|
久久国产视频网|
国产精品久久久久久久午夜片|
精品久久久无码中文字幕|
久久精品国产精品亚洲毛片|
精品国产日韩久久亚洲|
亚洲日韩欧美一区久久久久我
|
1000部精品久久久久久久久|
欧美va久久久噜噜噜久久|
亚洲人成电影网站久久|
欧美一级久久久久久久大片|
久久精品国产色蜜蜜麻豆|
久久精品成人|
国内精品伊人久久久久妇|