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

GreenCloudS

 
 
 

日志

 
 

SPOJ-8747. Substrings II && BZOJ-2555: SubString ( Suffix Automaton + Link Cut Tree )  

2014-04-20 12:55:00|  分类: LCT,后缀自动机, |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:

SPOJ-8747: http://www.spoj.com/problems/NSUBSTR2/

BZOJ-2555: http://www.lydsy.com/JudgeOnline/problem.php?id=2555


讨论一下每次插入对right集合的影响,我们发现唯一有变动的就是最后插入的那个节点的parent-tree上到root的所有状态都多了一个len+1,所以就用lct来维护parent-tree即可。


代码(写丑了。。。巨长。。QaQ):


SPOJ-8747:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define F( t ) father[ t ]

  • #define G( t ) F( F( t ) )

  • #define P( t ) parent[ splay_root( t ) ]

  • #define D( t ) delta[ t ]

  • #define V( t ) value[ t ]

  • #define C( t ) ( L( F( t ) ) == t )

  •  

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

  • #define par( t ) Node[ t ].parent

  • #define len( t ) Node[ t ].maxlen

  • #define N( t ) Node[ t ]

  •  

  • const int maxn = 80010 ;

  • const int maxv = maxn << 1 ;

  •  

  • struct link_cut_tree {

  •      

  •     int left[ maxv ] , right[ maxv ] , father[ maxv ] , parent[ maxv ] ;

  •     int delta[ maxv ] , value[ maxv ] ;

  •      

  •     link_cut_tree(  ) {

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

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

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

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

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

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

  •     }

  •      

  •     void pushdown( int t ) {

  •         if ( D( t ) && t ) {

  •             V( t ) += D( t ) ;

  •             D( L( t ) ) += D( t ) , D( R( t ) ) += D( t ) ;

  •             D( t ) = 0 ;

  •         }

  •     }

  •      

  •     void zag( int t ) {

  •         pushdown( t ) ; pushdown( R( t ) ) ;

  •         int k = R( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         F( R( t ) = L( k ) ) = t ;

  •         F( L( k ) = t ) = k ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     void zig( int t ) {

  •         pushdown( t ) ; pushdown( L( t ) ) ;

  •         int k = L( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         F( L( t ) = R( k ) ) = t ;

  •         F( R( k ) = t ) = k ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     void splay( int t ) {

  •         while ( F( t ) ) {

  •             if ( ! G( t ) ) if ( C( t ) ) zig( F( t ) ) ; else zag( F( t ) ) ;

  •             else {

  •                 if ( C( t ) ) {

  •                     if ( C( F( t ) ) ) zig( G( t ) ) ;

  •                     zig( F( t ) ) ;

  •                 } else {

  •                     if ( ! C( F( t ) ) ) zag( G( t ) ) ;

  •                     zag( F( t ) ) ;

  •                 }

  •             }

  •         }

  •     }

  •      

  •     int splay_root( int t ) {

  •         splay( t ) ;

  •         for ( ; L( t ) ; t = L( t ) ) ;

  •         return t ;

  •     }

  •      

  •     void Access( int t ) {

  •         int v = 0 ;

  •         do {

  •              splay( t ) ; pushdown( t ) ;

  •              F( R( t ) ) = 0 ; P( R( t ) ) = t ;

  •              F( R( t ) = v ) = t ;

  •              v = t ; t = P( t ) ;

  •         } while ( t ) ;

  •     }

  •      

  •     void Cut( int t ) {

  •         Access( t ) ;

  •         splay( t ) ; pushdown( t ) ;

  •         F( L( t ) ) = 0 ; P( t ) = 0 ; L( t ) = 0 ;

  •     }

  •      

  •     void Join( int t , int v ) {

  •         P( t ) = v ;

  •     }

  •      

  • } lct ;

  •  

  • struct suffix_automation {

  •      

  •     struct node {

  •         int child[ 26 ] , parent , maxlen ;

  •         node(  ) {

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

  •             parent = maxlen = 0 ;

  •         }

  •     } Node[ maxv ] ;

  •      

  •     int root , last , V , cnt[ maxv ] ;

  •      

  •     suffix_automation(  ) {

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

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

  •     }

  •      

  •     struct edge {

  •         edge *next ;

  •         int t ;

  •     } *head[ maxv ] ;

  •      

  •     int S[ maxv ] , Top , d[ maxv ] ;

  •      

  •     void INIT( char *s , int n ) {

  •         int ch , np , p , q , r ;

  •         for ( int i = 0 ; i ++ < n ; ) {

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

  •             np = ++ V , p = last ;

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

  •             for ( ; p && ! child( p , ch ) ; p = par( p ) ) child( p , ch ) = np ;

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

  •                 q = child( p , ch ) ;

  •                 if ( len( q ) == len( p ) + 1 ) par( np ) = q ; else {

  •                     r = ++ V ;

  •                     N( r ) = N( q ) ;

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

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

  •                     for ( ; p && child( p , ch ) == q ; p = par( p ) ) child( p , ch ) = r ;

  •                 }

  •             }

  •             last = np ;

  •         }

  •         for ( p = last ; p ; p = par( p ) ) cnt[ p ] = 1 ;

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

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

  •         Top = 0 ;

  •         edge *pt ;

  •         int i , j , v ;

  •         for ( i = 0 ; i ++ < V ; ) {

  •             for ( j = 0 ; j < 26 ; ++ j ) if ( child( i , j ) ) {

  •                 pt = new( edge ) ;

  •                 pt -> t = i , pt -> next = head[ child( i , j ) ] ;

  •                 head[ child( i , j ) ] = pt ;

  •                 ++ d[ i ] ;

  •             }

  •         }

  •         for ( i = 0 ; i < 26 ; ++ i ) if ( child( root , i ) ) {

  •             pt = new( edge ) ;

  •             pt -> t = root , pt -> next = head[ child( root , i ) ] ;

  •             head[ child( root , i ) ] = pt ;

  •             ++ d[ root ] ;

  •         }

  •         for ( i = 0 ; i ++ < V ; ) if ( ! d[ i ] ) {

  •             S[ ++ Top ] = i ;

  •         }

  •         while ( Top ) {

  •             v = S[ Top -- ] ;

  •             for ( i = 0 ; i < 26 ; ++ i ) if ( child( v , i ) ) {

  •                 cnt[ v ] += cnt[ child( v , i ) ] ;

  •             }

  •             for ( pt = head[ v ] ; pt ; pt = pt -> next ) {

  •                 if ( ! ( -- d[ pt -> t ] ) ) {

  •                     S[ ++ Top ] = pt -> t ;

  •                 }

  •             }

  •         }

  •         for ( i = 0 ; i ++ < V ; ) {

  •             lct.V( i ) = cnt[ i ] ;

  •             lct.parent[ lct.splay_root( i ) ] = par( i ) ;

  •         }

  •     }

  •      

  •     int query( int t ) {

  •         lct.Access( t ) ; lct.splay( t ) ; lct.pushdown( t ) ;

  •         return lct.V( t ) ;

  •     }

  •      

  •     void extend( int ch ) {

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

  •         for ( ; p && ! child( p , ch ) ; p = par( p ) ) child( p , ch ) = np ;

  •         if ( ! p ) {

  •             lct.Join( np , root ) ;

  •             par( np ) = root ;

  •         } else {

  •             q = child( p , ch ) ;

  •             if ( len( q ) == len( p ) + 1 ) {

  •                 lct.Join( np , q ) ;

  •                 par( np ) = q ;

  •             } else {

  •                 r = ++ V ;

  •                 N( r ) = N( q ) ; len( r ) = len( p ) + 1 ;

  •                 lct.V( r ) = query( q ) ;

  •                 lct.Join( r , par( r ) ) ;

  •                 lct.Join( np , r ) ; par( np ) = r ;

  •                 lct.Cut( q ) ; lct.Join( q , r ) ; par( q ) = r ;

  •                 for ( ; p && child( p , ch ) == q ; p = par( p ) ) child( p , ch ) = r ;

  •             }

  •         }

  •         last = np ;

  •         lct.Access( np ) ; lct.splay( np ) ; lct.D( np ) ++ ;

  •     }

  •      

  • } sam ;

  •  

  • char s[ maxn ] ;

  • int A , B , q , ans , n ;

  •  

  • int main(  ) {

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

  •     n = strlen( s + 1 ) ;

  •     sam.INIT( s , n ) ;

  •     scanf( "%d%d%d" , &q , &A , &B ) ;

  •     int t , i ;

  •     while ( q -- ) {

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

  •         n = strlen( s + 1 ) ;

  •         for ( t = sam.root , i = 1 ; i <= n ; ++ i ) {

  •             if ( ! sam.child( t , s[ i ] - 'a' ) ) {

  •                 t = 0 ; continue ;

  •             } else t = sam.child( t , s[ i ] - 'a' ) ;

  •         }

  •         if ( ! t ) ans = 0 ; else ans = sam.query( t ) ;

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

  •         sam.extend( ( A * ans + B ) % 26 ) ;

  •     }

  •     return 0 ;

  • }




BZOJ-2555:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define F( t ) father[ t ]

  • #define G( t ) F( F( t ) )

  • #define P( t ) parent[ splay_root( t ) ]

  • #define D( t ) delta[ t ]

  • #define V( t ) value[ t ]

  • #define C( t ) ( L( F( t ) ) == t )

  •  

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

  • #define par( t ) Node[ t ].parent

  • #define len( t ) Node[ t ].maxlen

  • #define N( t ) Node[ t ]

  •  

  • const int maxn = 601000 ;

  • const int maxv = maxn << 1 ;

  •  

  • struct link_cut_tree {

  •      

  •     int left[ maxv ] , right[ maxv ] , father[ maxv ] , parent[ maxv ] ;

  •     int delta[ maxv ] , value[ maxv ] ;

  •      

  •     link_cut_tree(  ) {

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

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

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

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

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

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

  •     }

  •      

  •     void pushdown( int t ) {

  •         if ( D( t ) && t ) {

  •             V( t ) += D( t ) ;

  •             D( L( t ) ) += D( t ) , D( R( t ) ) += D( t ) ;

  •             D( t ) = 0 ;

  •         }

  •     }

  •      

  •     void zag( int t ) {

  •         pushdown( t ) ; pushdown( R( t ) ) ;

  •         int k = R( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         F( R( t ) = L( k ) ) = t ;

  •         F( L( k ) = t ) = k ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     void zig( int t ) {

  •         pushdown( t ) ; pushdown( L( t ) ) ;

  •         int k = L( t ) , u = F( t ) ; bool flag = C( t ) ;

  •         F( L( t ) = R( k ) ) = t ;

  •         F( R( k ) = t ) = k ;

  •         if ( F( k ) = u ) if ( flag ) L( u ) = k ; else R( u ) = k ;

  •     }

  •      

  •     void splay( int t ) {

  •         while ( F( t ) ) {

  •             if ( ! G( t ) ) if ( C( t ) ) zig( F( t ) ) ; else zag( F( t ) ) ;

  •             else {

  •                 if ( C( t ) ) {

  •                     if ( C( F( t ) ) ) zig( G( t ) ) ;

  •                     zig( F( t ) ) ;

  •                 } else {

  •                     if ( ! C( F( t ) ) ) zag( G( t ) ) ;

  •                     zag( F( t ) ) ;

  •                 }

  •             }

  •         }

  •     }

  •      

  •     int splay_root( int t ) {

  •         splay( t ) ;

  •         for ( ; L( t ) ; t = L( t ) ) ;

  •         return t ;

  •     }

  •      

  •     void Access( int t ) {

  •         int v = 0 ;

  •         do {

  •              splay( t ) ; pushdown( t ) ;

  •              F( R( t ) ) = 0 ; P( R( t ) ) = t ;

  •              F( R( t ) = v ) = t ;

  •              v = t ; t = P( t ) ;

  •         } while ( t ) ;

  •     }

  •      

  •     void Cut( int t ) {

  •         Access( t ) ;

  •         splay( t ) ; pushdown( t ) ;

  •         F( L( t ) ) = 0 ; P( t ) = 0 ; L( t ) = 0 ;

  •     }

  •      

  •     void Join( int t , int v ) {

  •         P( t ) = v ;

  •     }

  •      

  • } lct ;

  •  

  • struct suffix_automation {

  •      

  •     struct node {

  •         int child[ 26 ] , parent , maxlen ;

  •         node(  ) {

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

  •             parent = maxlen = 0 ;

  •         }

  •     } Node[ maxv ] ;

  •      

  •     int root , last , V , cnt[ maxv ] ;

  •      

  •     suffix_automation(  ) {

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

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

  •     }

  •      

  •     struct edge {

  •         edge *next ;

  •         int t ;

  •     } *head[ maxv ] ;

  •      

  •     int S[ maxv ] , Top , d[ maxv ] ;

  •      

  •     void INIT( char *s , int n ) {

  •         int ch , np , p , q , r ;

  •         for ( int i = 0 ; i ++ < n ; ) {

  •             ch = s[ i ] - 'A' ;

  •             np = ++ V , p = last ;

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

  •             for ( ; p && ! child( p , ch ) ; p = par( p ) ) child( p , ch ) = np ;

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

  •                 q = child( p , ch ) ;

  •                 if ( len( q ) == len( p ) + 1 ) par( np ) = q ; else {

  •                     r = ++ V ;

  •                     N( r ) = N( q ) ;

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

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

  •                     for ( ; p && child( p , ch ) == q ; p = par( p ) ) child( p , ch ) = r ;

  •                 }

  •             }

  •             last = np ;

  •         }

  •         for ( p = last ; p ; p = par( p ) ) cnt[ p ] = 1 ;

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

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

  •         Top = 0 ;

  •         edge *pt ;

  •         int i , j , v ;

  •         for ( i = 0 ; i ++ < V ; ) {

  •             for ( j = 0 ; j < 26 ; ++ j ) if ( child( i , j ) ) {

  •                 pt = new( edge ) ;

  •                 pt -> t = i , pt -> next = head[ child( i , j ) ] ;

  •                 head[ child( i , j ) ] = pt ;

  •                 ++ d[ i ] ;

  •             }

  •         }

  •         for ( i = 0 ; i < 26 ; ++ i ) if ( child( root , i ) ) {

  •             pt = new( edge ) ;

  •             pt -> t = root , pt -> next = head[ child( root , i ) ] ;

  •             head[ child( root , i ) ] = pt ;

  •             ++ d[ root ] ;

  •         }

  •         for ( i = 0 ; i ++ < V ; ) if ( ! d[ i ] ) {

  •             S[ ++ Top ] = i ;

  •         }

  •         while ( Top ) {

  •             v = S[ Top -- ] ;

  •             for ( i = 0 ; i < 26 ; ++ i ) if ( child( v , i ) ) {

  •                 cnt[ v ] += cnt[ child( v , i ) ] ;

  •             }

  •             for ( pt = head[ v ] ; pt ; pt = pt -> next ) {

  •                 if ( ! ( -- d[ pt -> t ] ) ) {

  •                     S[ ++ Top ] = pt -> t ;

  •                 }

  •             }

  •         }

  •         for ( i = 0 ; i ++ < V ; ) {

  •             lct.V( i ) = cnt[ i ] ;

  •             lct.parent[ lct.splay_root( i ) ] = par( i ) ;

  •         }

  •     }

  •      

  •     int query( int t ) {

  •         lct.Access( t ) ; lct.splay( t ) ; lct.pushdown( t ) ;

  •         return lct.V( t ) ;

  •     }

  •      

  •     void extend( int ch ) {

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

  •         for ( ; p && ! child( p , ch ) ; p = par( p ) ) child( p , ch ) = np ;

  •         if ( ! p ) {

  •             lct.Join( np , root ) ;

  •             par( np ) = root ;

  •         } else {

  •             q = child( p , ch ) ;

  •             if ( len( q ) == len( p ) + 1 ) {

  •                 lct.Join( np , q ) ;

  •                 par( np ) = q ;

  •             } else {

  •                 r = ++ V ;

  •                 N( r ) = N( q ) ; len( r ) = len( p ) + 1 ;

  •                 lct.V( r ) = query( q ) ;

  •                 lct.Join( r , par( r ) ) ;

  •                 lct.Join( np , r ) ; par( np ) = r ;

  •                 lct.Cut( q ) ; lct.Join( q , r ) ; par( q ) = r ;

  •                 for ( ; p && child( p , ch ) == q ; p = par( p ) ) child( p , ch ) = r ;

  •             }

  •         }

  •         last = np ;

  •         lct.Access( np ) ; lct.splay( np ) ; lct.D( np ) ++ ;

  •     }

  •      

  • } sam ;

  •  

  • void trans( char *s , int mask ) {

  •     for ( int i = 0 , l = strlen( s ) ; i < l ; ++ i ) {

  •         mask = ( mask * 131 + i ) % l ;

  •         swap( s[ i ] , s[ mask ] ) ;

  •     }

  • }

  •  

  • char s[ maxn ] ;

  • int A , B , q , ans , n ;

  •  

  • int main(  ) {

  •     scanf( "%d" , &q ) ;

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

  •     n = strlen( s + 1 ) ;

  •     sam.INIT( s , n ) ;

  •     int mask = 0 ;

  •     int t , i , ans , l ;

  •     while ( q -- ) {

  •         scanf( "%s" , s ) ;

  •         if ( s[ 0 ] == 'Q' ) {

  •             scanf( "%s" , s ) ;

  •             trans( s , mask ) ;

  •             for ( t = sam.root , i = 0 , l = strlen( s ) ; i < l ; ++ i ) {

  •                 if ( ! sam.child( t , s[ i ] - 'A' ) ) {

  •                     t = 0 ; break ;

  •                 } else t = sam.child( t , s[ i ] - 'A' ) ;

  •             }

  •             if ( ! t ) ans = 0 ; else ans = sam.query( t ) ;

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

  •             mask ^= ans ;

  •         } else {

  •             scanf( "%s" , s ) ;

  •             trans( s , mask ) ;

  •             for ( i = 0 , l = strlen( s ) ; i < l ; ++ i ) {

  •                 sam.extend( s[ i ] - 'A' ) ;

  •             }

  •         }

  •     }

  •     return 0 ;

  • }



  评论这张
 
阅读(10)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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