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

GreenCloudS

 
 
 

日志

 
 

SPOJ-7258. Lexicographical Substring Search(Suffix Automaton)  

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

  下载LOFTER 我的照片书  |

题目:http://www.spoj.com/problems/SUBLEX/


明显,如果按照字典序DFS整个自动机便可以按字典序生成出所有子串,那么要求k小子串的话就先DP一下,令dp(v)表示从v状态开始遍历可以得到的子串数目,那么dp( v )=sigma( dp( child( v ) ) + 1 ),于是乎每次查找的时候遍历一下就可以了。


PS:这道题我整整玩了一天常数才过了。。。无语的发现其实puts()输出字符串比putchar还快额。。。刷出满屏的TLE真是不好意思。。。(SPOJ太慢了。。。*N)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • 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 =90010;

  • 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;

  •  

  • typedef unsigned int uint ;

  •  

  • uint sum[ maxv ];

  •  

  • int s[ maxn ], n , m ;

  •  

  • int trans[ maxv ][26], num[ maxv ], d[ maxv ];

  • char tchr[ maxv ][26];

  •  

  • struct edge{

  •         edge *next ;

  •         int t ;

  • }*head[ maxv ];

  •  

  • int S[ maxv ], Top =0;

  •  

  • void cal(  ){

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

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

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

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

  •         int i , j ;

  •         edge *p ;

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

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

  •                        trans[ i ][ num[ i ]]=C( i , j );

  •                        tchr[ i ][ num[ i ]++]='a'+ j ;

  •                        ++ d[ i ];

  •                        p =new( edge );

  •                        p -> t = i , p -> next = head[C( i , j )];

  •                        head[C( i , j )]= p ;

  •                }

  •         }

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

  •                trans[ root ][ num[ root ]]=C( root , i );

  •                tchr[ root ][ num[ root ]++]='a'+ i ;

  •                ++ d[ root ];

  •                p =new( edge );

  •                p -> t = root , p -> next = head[C( root , i )];

  •                head[C( root , i )]= p ;

  •         }

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

  •                S[++ Top ]= i ;

  •         }

  •         int v ;

  •         while( Top ){

  •                v = S[ Top --];

  •                for( i =0; i < num[ v ];++ i ){

  •                        sum[ v ]+= sum[ trans[ v ][ i ]]+1;

  •                }

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

  •                        if(!(-- d[ p -> t ])) S[++ Top ]= p -> t ;

  •                }

  •         }

  • }

  •  

  • char ans[ maxn ];

  •  

  • void build(  ){

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

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

  •                ch = s[ i ];

  •                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{

  •                 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( np )=P( q )= r ;

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

  •                 }

  •          }

  •          last= np ;

  •         }

  • }

  •  

  • void getstr(int&len ){

  •         int ch ;

  •         for( ch =getchar(  ); ch <'a'|| ch >'z'; ch =getchar(  ));

  •         s[ len =1]= ch -'a';

  •         for( ch =getchar(  ); ch >='a'&& ch <='z'; ch =getchar(  )){

  •                s[++ len ]= ch -'a';

  •         }

  • }

  •  

  • int main(  ){

  •         getstr( n );

  •         build(  );

  •         cal(  );

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

  •         while( m --){

  •                uint k ;scanf("%u",&k );

  •                if( k > sum[ root ]){

  •                        puts("WRONG");

  •                        continue;

  •                }

  •                char*p = ans ;

  •                int i ;

  •                for(int t = root , q ; k ;){

  •                        for( i =0; i < num[ t ];++ i ){

  •                                -- k ;

  •                                q = trans[ t ][ i ];

  •                                if( k > sum[ q ]) k -= sum[ q ];else{

  •                                       *( p ++)= tchr[ t ][ i ];

  •                                       t= q ;

  •                                       break;

  •                                }

  •                        }

  •                }

  •                *p =0;

  •                puts( ans );

  •         }

  •         return 0;

  • }


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

历史上的今天

评论

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

页脚

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