• <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电影|
中文字幕热久久久久久久|
久久久久亚洲精品中文字幕|
成人国内精品久久久久一区|
99精品久久精品一区二区|
一本大道久久东京热无码AV|
四虎久久影院|
亚洲国产精品综合久久网络
|
品成人欧美大片久久国产欧美...|
亚洲午夜久久久久久久久久|
一本色道久久88精品综合|
亚洲精品tv久久久久久久久久|
欧美粉嫩小泬久久久久久久|
亚洲美日韩Av中文字幕无码久久久妻妇
|
2021国内精品久久久久久影院|
久久99精品国产99久久6|
国产福利电影一区二区三区久久久久成人精品综合
|
999久久久国产精品|
99久久婷婷国产综合精品草原|
久久激情亚洲精品无码?V|
亚洲欧美成人久久综合中文网
|
久久99精品久久久久久齐齐|
久久黄视频|
少妇无套内谢久久久久|
欧美黑人激情性久久|
精品人妻久久久久久888|
国产福利电影一区二区三区久久久久成人精品综合
|
国产一区二区精品久久岳|
欧美午夜A∨大片久久
|
亚洲国产精品成人久久蜜臀
|
99精品国产在热久久|
精品人妻伦一二三区久久|
精品国产青草久久久久福利|
国产精品久久久久影院色|
久久免费香蕉视频|
国产麻豆精品久久一二三|
久久成人精品|
a高清免费毛片久久|
久久精品视频一|
97精品伊人久久久大香线蕉|
狠狠色噜噜色狠狠狠综合久久|