• <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)  編輯 收藏 引用  所屬分類: 字符串處理 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久午夜无码鲁丝片秋霞|
久久99国产精品一区二区|
亚洲第一永久AV网站久久精品男人的天堂AV|
国产精品久久久久久影院
|
国产日韩久久免费影院|
国产 亚洲 欧美 另类 久久|
国产精品青草久久久久福利99|
热综合一本伊人久久精品|
久久精品国产清高在天天线|
久久精品国产清自在天天线|
色欲久久久天天天综合网|
成人精品一区二区久久久|
久久综合色老色|
久久99国产精品一区二区|
18岁日韩内射颜射午夜久久成人|
99精品久久久久久久婷婷|
久久丫忘忧草产品|
久久精品国产色蜜蜜麻豆|
久久精品国产亚洲AV电影|
亚洲人成网站999久久久综合|
成人国内精品久久久久影院|
久久久久久伊人高潮影院|
九九久久精品无码专区|
99久久er这里只有精品18|
2020久久精品亚洲热综合一本|
久久精品国产久精国产|
漂亮人妻被黑人久久精品|
久久久久久久女国产乱让韩|
亚洲精品视频久久久|
亚洲欧美久久久久9999|
精品国产婷婷久久久|
狠狠色综合网站久久久久久久|
99久久99这里只有免费费精品|
亚洲精品乱码久久久久久久久久久久
|
日本强好片久久久久久AAA|
一本色道久久88综合日韩精品|
久久se精品一区二区影院|
国产成人香蕉久久久久|
成人精品一区二区久久久|
久久久久亚洲AV无码专区网站
|
亚洲精品乱码久久久久久蜜桃不卡
|