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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1396: 识别子串(后缀自动机+堆)  

2014-04-22 20:03:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1396


首先预处理出对于每个i,最短的len( i )满足s[ i - len( i ) + 1 ... i ]在s中只出现一次,这个后缀自动机O(n)解决,然后对于每个位置x,枚举所在识别子串的右端点r,那么对于最短识别子串s[ a ... b ]有两种情况,分别为len( r ) > x && len( r ) <= x , 对于后者明显直接找出所有的len(r)最小即可,这个可以堆维护,对于前者我们可以认识到以r为右端点的最短识别子串的左端点一定是x,那么就开一个变量维护一下最小的r即可,总复杂度:O(n log n)。

(好久没写过这么完整的题解了,当成是为了GDOI和CTSC攒RP吧。。。求省选不挂。。。)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  • #include <stack>

  • #include <queue>

  •  

  • using namespace std ;

  •  

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

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

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

  • #define N( t ) Node[ t ]

  •  

  • const int maxn = 100100 ;

  • const int inf = 100000000 ;

  • const int maxv = maxn << 1 ;

  •  

  • struct node {

  •     int parent , child[ 26 ] , maxlen ;

  •     node(  ) {

  •         parent = maxlen = 0 ;

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

  •     }

  • } Node[ maxv ] ;

  •  

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

  •  

  • void extend( int ch ) {

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

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

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

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

  •         q = C( p , ch ) ;

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

  •             r = ++ V ;

  •             N( r ) = N( q ) ;

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

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

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

  •         }

  •     }

  •     last = np ;

  • }

  •  

  • vector < int > E[ maxv ] ;

  • int sum[ maxv ] , d[ maxv ] ;

  • stack < int > S ;

  •  

  • void cal(  ) {

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

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

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

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

  •             E[ C( i , j ) ].push_back( i ) ;

  •             ++ d[ i ] ;

  •         }

  •     }

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

  •         E[ C( root , i ) ].push_back( root ) ;

  •         ++ d[ root ] ;

  •     }

  •     for ( int i = last ; i ; i = P( i ) ) sum[ i ] = 1 ;

  •     for ( int i = 0 ; i ++ < V ; ) if ( ! d[ i ] ) S.push( i ) ;

  •     while ( ! S.empty(  ) ) {

  •         int v = S.top(  ) ; S.pop(  ) ;

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

  •             sum[ v ] += sum[ C( v , i ) ] ;

  •         }

  •         for ( vector < int > :: iterator p = E[ v ].begin(  ) ; p != E[ v ].end(  ) ; ++ p ) {

  •             if ( ! ( -- d[ *p ] ) ) S.push( *p ) ;

  •         }

  •     }

  •     for ( int i = 0 ; i ++ < V ; ) E[ i ].clear(  ) ;

  •     E[ root ].clear(  ) ;

  • }

  •  

  • char s[ maxn ] ;

  • int n , LEN[ maxn ] ;

  •  

  • int state[ maxv ] ;

  •  

  • void dfs( int now , int len ) {

  •     if ( sum[ now ] == 1 ) len = min( len , L( P( now ) ) + 1 ) ;

  •     state[ now ] = len ;

  •     for ( vector < int > :: iterator p = E[ now ].begin(  ) ; p != E[ now ].end(  ) ; ++ p ) {

  •         dfs( *p , len ) ;

  •     }

  • }

  •  

  • struct seg {

  •     int r , len ;

  •     seg( int _r , int _len ) : r( _r ) , len( _len ) {

  •  

  •     }

  •     bool operator < ( const seg &a ) const {

  •         return len > a.len ;

  •     }

  • } ;

  • priority_queue < seg > q ;

  • vector < int > ve[ maxn ] ;

  •  

  • int ans[ maxn ] ;

  •  

  • int main(  ) {

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

  •     n = strlen( s + 1 ) ;

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

  •     cal(  ) ;

  •     for ( int i = 0 ; i ++ < V ; ) E[ P( i ) ].push_back( i ) ;

  •     dfs( root , inf ) ;

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

  •         LEN[ i ] = state[ t = C( t , s[ i ] - 'a' ) ] ;

  •         if ( LEN[ i ] < inf ) ve[ i - LEN[ i ] ].push_back( i ) ;

  •     }

  •     for ( int i = n , temp = inf ; i ; -- i ) {

  •         q.push( seg( i , LEN[ i ] ) ) ;

  •         for ( vector < int > :: iterator p = ve[ i ].begin(  ) ; p != ve[ i ].end(  ) ; ++ p ) {

  •             temp = min( temp , *p ) ;

  •         }

  •         seg rec = q.top(  ) ;

  •         while ( rec.r - rec.len >= i ) {

  •             q.pop(  ) ;

  •             rec = q.top(  ) ;

  •         }

  •         ans[ i ] = min( temp - i + 1 , rec.len ) ;

  •     }

  •     for ( int i = 0 ; i ++ < n ; ) printf( "%d\n" , ans[ i ] ) ;

  •     return 0 ;

  • }



  评论这张
 
阅读(5)| 评论(7)
推荐 转载

历史上的今天

评论

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

页脚

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