• <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++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲国产成人久久综合野外|
无码精品久久一区二区三区|
久久久久亚洲国产|
亚洲AⅤ优女AV综合久久久|
免费精品久久天干天干|
久久精品国产亚洲AV电影|
99久久综合国产精品二区|
无码任你躁久久久久久老妇App|
久久午夜夜伦鲁鲁片免费无码影视
|
99久久免费国产特黄|
欧美久久亚洲精品|
久久国产高潮流白浆免费观看|
久久国产高清一区二区三区|
久久天天躁狠狠躁夜夜躁2O2O|
久久综合五月丁香久久激情|
色综合久久天天综合|
久久久久亚洲av无码专区喷水
|
亚洲狠狠婷婷综合久久久久|
日韩中文久久|
国产精品伦理久久久久久|
亚洲va久久久噜噜噜久久天堂|
激情综合色综合久久综合|
久久国产亚洲精品麻豆|
久久精品国产第一区二区三区
|
国产精品久久久久久搜索|
99久久香蕉国产线看观香|
青青青青久久精品国产h久久精品五福影院1421|
亚洲精品乱码久久久久久蜜桃图片
|
99久久99久久精品免费看蜜桃|
久久频这里精品99香蕉久|
香蕉99久久国产综合精品宅男自
|
久久久亚洲AV波多野结衣|
欧美日韩久久中文字幕|
久久久久国色AV免费看图片|
久久人人爽人人爽人人片AV高清|
国产精品青草久久久久福利99
|
久久人人爽人人爽人人片AV不|
人妻中文久久久久|
一本久久免费视频|
久久精品国产2020|
久久精品国产亚洲AV电影|