• <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: 4440K
            
            Time: 657MS
        
            
        
            
            Language: C++
            
            Result: Accepted
        
            
                

            

            #include <stdio.h>
            #include             <cstring>

            const int MAX = 201000 ;

            int n ;

            int cnt[MAX] , array[4][MAX] , *rank , *nrank , *sa , *nsa , h[MAX] ;
            char SText[MAX] ;

            void CreateSuffix()
            {
                            int i , k ;
                rank             = array[0] ;
                nrank             = array[1] ;
                sa             = array[2] ;
                nsa             = array[3] ;

                            for ( i = 0 ; i < n ; i++ )
                            {
                    cnt[SText[i]]            ++ ;
                }
                            for ( i = 1 ; i < 256 ; i++ )
                            {
                    cnt[i]             += cnt[i - 1] ;
                }
                            for ( i = n - 1 ; i >= 0 ; i-- )
                            {
                    sa[            --cnt[SText[i]]] = i ;
                }
                            for ( rank[sa[0]] = 0 , i = 1 ; i < n ; i++ )
                            {
                    rank[sa[i]]             = rank[sa[i - 1]] ;
                                if ( SText[sa[i]] != SText[sa[i - 1]] )
                                {
                        rank[sa[i]]            ++ ;
                    }
                }

                            for ( k = 1 ; k < n && rank[sa[n - 1]] < n - 1; k *= 2 )
                            {
                                for ( i = 0 ; i < n ; i++ )
                        cnt[rank[sa[i]]]             = i + 1 ;
                                for ( i = n - 1 ; i >= 0 ; i-- )
                                {
                                    if ( sa[i] - k >= 0 )
                                    {
                            nsa[            --cnt[rank[sa[i] - k]]] = sa[i] - k ;
                        }
                    }

                                for ( i = n - k ; i < n ; i++ )
                                {
                        nsa[            --cnt[rank[i]]] = i ;
                    }

                                for ( nrank[nsa[0]] = 0 , i = 1 ; i < n ; i++ )
                                {
                        nrank[nsa[i]]             = nrank[nsa[i - 1]] ;
                                    if ( rank[nsa[i]] != rank[nsa[i - 1]]
                                        || rank[nsa[i] + k] != rank[nsa[i - 1] + k] )
                                    {
                            nrank[nsa[i]]            ++ ;
                        }
                    }

                                int *t = rank ; rank = nrank ; nrank = t ;
                    t             = sa ; sa = nsa ; nsa = t ;
                }
            }

            void CalHeight()
            {
                            int i , j , k ;
                            for ( i = 0 , k = 0 ; i < n ; i++ )
                            {
                                if ( rank[i] == n - 1 )
                        h[rank[i]]             = k = 0 ;
                                else {
                                    if ( k > 0 ) k-- ;
                        j             = sa[rank[i] + 1] ;
                                    for ( ; SText[i + k] == SText[j + k] ; k++ ) ;
                        h[rank[i]]             = k ;
                    }
                }
            }

            int main()
            {
                            char ks[MAX] ;
                            int i , j , k , len , p1 , p2 , ans = 0 ;

                            //scanf("%s", &SText) ;
                gets(SText) ;
                gets(ks) ;
                            //scanf("%s", &ks ) ;

                len             = strlen(SText) ;
                SText[len]             = '#' ;

                strcat( SText , ks ) ;

                n             = strlen ( SText ) ;
                SText[n            ++] = 0 ;
                memset(cnt,             0, sizeof(cnt)) ;

                CreateSuffix() ;
                CalHeight() ;

                            for ( i = 0 ; i < n - 1 ; i++ )
                            {
                    j             = sa[i]; 
                                if(j < len)p1 = 1; 
                                else p1 = -1; 
                    
                    k             = sa[i+1]; 
                                if(k < len)p2 = 1; 
                                else p2 = -1; 
                    
                                if(p1*p2<1 && h[i]>ans) 
                        ans             = h[i]; 
                }

                printf(            "%d\n", ans) ;
                
                            return 0 ;
            }
            

	
            
	
	
            
		posted on 2008-11-08 14:17 巫 閱讀(588) 評論(0)  編輯 收藏 引用  所屬分類: 字符串處理 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久久久亚洲精品天堂久久久久久
|
久久精品无码一区二区app|
97超级碰碰碰久久久久|
AA级片免费看视频久久|
亚洲性久久久影院|
国产精品美女久久久久网|
亚洲第一永久AV网站久久精品男人的天堂AV
|
久久人爽人人爽人人片AV|
欧美亚洲另类久久综合|
色狠狠久久综合网|
久久精品国产影库免费看|
久久精品免费全国观看国产|
996久久国产精品线观看|
久久乐国产精品亚洲综合|
精品无码久久久久国产|
久久国产精品无|
国产一区二区精品久久凹凸|
久久天天躁狠狠躁夜夜96流白浆|
久久精品视频91|
狠色狠色狠狠色综合久久|
久久精品国产日本波多野结衣|
99热热久久这里只有精品68|
久久成人国产精品|
亚洲色婷婷综合久久|
偷偷做久久久久网站|
青青草原综合久久大伊人导航|
久久精品这里热有精品|
久久久久亚洲AV片无码下载蜜桃|
久久久这里只有精品加勒比|
久久久久无码精品国产app|
久久精品一区二区国产|
久久久久亚洲av无码专区喷水|
久久精品亚洲AV久久久无码|
久久这里的只有是精品23|
亚洲欧美精品一区久久中文字幕|
久久亚洲国产精品五月天婷|
香蕉久久永久视频|
精产国品久久一二三产区区别|
2021国产精品午夜久久
|
亚洲精品乱码久久久久久中文字幕|
亚洲人成无码www久久久|