• <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屬性是記錄什么的  回復  更多評論
						
            
						  
					
            
				
            
				
            
			

            




            






            

				

            



    
    







            
	   
	



国产精品久久久久久福利69堂|
91久久精品视频|
蜜臀av性久久久久蜜臀aⅴ|
色综合久久久久综合体桃花网|
久久成人国产精品二三区|
午夜精品久久影院蜜桃|
欧美黑人又粗又大久久久|
国内精品久久久久影院网站|
久久精品国产亚洲AV不卡|
国产福利电影一区二区三区，免费久久久久久久精
|
人妻久久久一区二区三区|
久久国产美女免费观看精品
|
久久精品毛片免费观看|
欧美久久天天综合香蕉伊|
国内精品伊人久久久久|
亚洲乱码精品久久久久..|
精品无码久久久久久国产|
久久本道伊人久久|
午夜精品久久久久久久久|
久久国产亚洲精品|
欧美精品丝袜久久久中文字幕
|
久久国产热这里只有精品|
99re久久精品国产首页2020|
奇米影视7777久久精品|
久久久久国产精品人妻|
亚洲另类欧美综合久久图片区|
久久久久综合网久久|
狠狠色丁香久久综合五月|
国产午夜免费高清久久影院|
无码久久精品国产亚洲Av影片|
久久久SS麻豆欧美国产日韩|
色欲综合久久躁天天躁|
精品国产91久久久久久久a|
国产福利电影一区二区三区，免费久久久久久久精
|
国产91色综合久久免费|
欧美熟妇另类久久久久久不卡
|
一本色道久久88综合日韩精品|
久久亚洲AV无码西西人体|
午夜精品久久久久久久无码|
亚洲精品成人久久久|
久久精品国产亚洲av麻豆蜜芽|