注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

SPOJ-1811. Longest Common Substring && 1812. Longest Common Substring II (后缀自动机)  

2014-04-17 21:10:00|  分类: SPOJ,后缀自动机, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:

http://www.spoj.com/problems/LCS/

http://www.spoj.com/problems/LCS2/


两道水题,据说SA之类的常数卡得挺紧的,于是乎顺手拿过来练手了一下SAM。。。


代码:

1811:

  • #include <cstdio>
  • #include <algorithm>
  • #include <cstring>
  •  
  • using namespace std ;
  •  
  • #define C( t , x ) sam[ t ].ch[ x ]
  • #define P( t ) sam[ t ].parent
  • #define L( t ) sam[ t ].len
  • #define N( t ) sam[ t ]
  •  
  • #define check( ch ) ( ch >= 'a' && ch <= 'z' )
  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )
  •  
  • const int maxn = 251000 ;
  • const int maxv = maxn << 1 ;
  •  
  • struct node {
  •         int ch[ 26 ] , parent , len ;
  •         node(  ) {
  •                memset( ch , 0 , sizeof( ch ) ) ;
  •                parent = len = 0 ; 
  •         }
  • } sam[ maxv ] ;
  •  
  • int root = maxv - 1 , V = 0 , last = maxv - 1 ; 
  •  
  • void add( int ch , int l ) {
  •         int p = last , np = ++ V ; 
  •         L( np ) = l ;
  •         for ( ; ! C( p , ch ) && p ; p = P( p ) ) C( p , ch ) = np ;
  •         if ( ! p ) P( np ) = root ; else {
  •                int q = C( p , ch ) ;
  •                if ( L( q ) == L( p ) + 1 ) P( np ) = q ; else {
  •                        int r = ++ V ;
  •                        N( r ) = N( q ) ;
  •                        L( r ) = L( p ) + 1 ; 
  •                        P( np ) = P( q ) = r ; 
  •                        for ( ; p && C( p , ch ) == q ; p = P( p ) ) C( p , ch ) = r ; 
  •                }
  •         }
  •         last = np ;
  • }
  •  
  • int s[ maxn ] , slen ;
  •  
  • void getstr(  ) {
  •         slen = 0 ; 
  •         int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ; 
  •         s[ ++ slen ] = ch - 'a' ;
  •         for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {
  •                s[ ++ slen ] = ch - 'a' ;
  •         }
  • }
  •  
  • int main(  ) {
  •         getstr(  ) ;
  •         rep( i , slen ) add( s[ i ] , i ) ;
  •         int mlen = 0 , ans = 0 , t = root ;
  •         getstr(  ) ;
  •         rep( i , slen ) {
  •                int ch = s[ i ] ;
  •                if ( C( t , ch ) ) ++ mlen , t = C( t , ch ) ; else {
  •                        for ( ; t && ! C( t , ch ) ; t = P( t ) ) ;
  •                        if ( ! t ) t = root , mlen = 0 ; else {
  •                                mlen = L( t ) + 1 ;
  •                                t = C( t , ch ) ;
  •                        }
  •                }
  •                ans = max( ans , mlen ) ;
  •         }
  •         printf( "%d\n" , ans ) ;
  •         return 0 ; 
  • }



1812:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define P( t ) sam[ t ].parent

  • #define C( t , x ) sam[ t ].child[ x ]

  • #define N( t ) sam[ t ]

  • #define F( t ) sam[ t ].fun

  • #define L( t ) sam[ t ].maxlen

  •  

  • const int maxn = 100100 ;

  • const int maxv = maxn << 1 ; 

  •  

  • struct node {

  •         int child[ 26 ] , parent , fun , maxlen ;

  •         node(  ) {

  •                memset( child , 0 , sizeof( child ) ) ;

  •                parent = fun = maxlen = 0 ; 

  •         }

  • } sam[ maxv ] ;

  •  

  • int last = maxv - 1 , root = maxv - 1 , V = 0 ; 

  •  

  • void extend( int ch ) {

  •         int np = ++ V , p = last ; 

  •         L( np ) = L( p ) + 1 ; 

  •         for ( ; p && ! C( p , ch ) ; p = P( p ) ) C( p , ch ) = np ; 

  •         if ( ! p ) P( np ) = root ; else {

  •                int q = C( p , ch ) ;

  •                if ( L( q ) == L( p ) + 1 ) P( np ) = q ; else {

  •                        int r = ++ V ;

  •                        N( r ) = N( q ) ; 

  •                        L( r ) = L( p ) + 1 ;

  •                        P( np ) = P( q ) = r ; 

  •                        for ( ; p && C( p , ch ) == q ; p = P( p ) ) C( p , ch ) = r ; 

  •                }

  •         }

  •         last = np ;

  • }

  •  

  • char s[ maxn ] ;

  • int dp[ maxv ] , len ;

  •  

  • void update( int &x , int val ) {

  •         x = max( x , val ) ;

  • }

  •  

  • int main(  ) {

  •         scanf( "%s" , s + 1 ) ;

  •         len = strlen( s + 1 ) ;

  •         for ( int i = 0 ; i ++ < len ; ) extend( s[ i ] - 'a' ) ;

  •         for ( int i = 0 ; i <= V ; ++ i ) dp[ i ] = L( i ) ;

  •         while ( scanf( "%s" , s + 1 ) != EOF ) {

  •                len = strlen( s + 1 ) ;

  •                for ( int i = 0 ; i <= V ; ++ i ) F( i ) = 0 ; 

  •                for ( int i = 1 , temp = 0 , t = root ; i <= len ; ++ i ) {

  •                        int ch = s[ i ] - 'a' ;

  •                        if ( C( t , ch ) ) update( F( t = C( t , ch ) ) , ++ temp ) ; else {

  •                                for ( ; t && ! C( t , ch ) ; t = P( t ) ) ;

  •                                if ( ! t ) t = root , temp = 0 ; else {

  •                                       temp = L( t ) + 1 ; 

  •                                       update( F( t = C( t , ch ) ) , temp ) ;

  •                                }

  •                        }

  •                }

  •                for ( int i = V ; i ; -- i ) update( F( P( i ) ) , F( i ) ) ;

  •                for ( int i = 0 ; i <= V ; ++ i ) dp[ i ] = min( dp[ i ] , F( i ) ) ;

  •         }

  •         int ans = 0 ; 

  •         for ( int i = 0 ; i <= V ; ++ i ) update( ans , dp[ i ] ) ;

  •         printf( "%d\n" , ans ) ;

  •         return 0 ; 

  • }




  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017