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

GreenCloudS

 
 
 

日志

 
 

SPOJ-8222. Substrings(Suffix Automaton)  

2014-04-19 19:13:00|  分类: oi,数据结构,spoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


首先考虑CLJ课件里面提及到的right集合的大小怎么求,我们发现对于right(s)集合中的每一个元素,恰好对应从s状态出发,到达终结态的一条路径(终结态即last在parent树上到根的路径上的状态),那么right(s)集合的大小就成了从s出发到达终结态的路径个数,那么这个就可以用O(n)的拓扑DP算出,然后就把算出的right大小进行更新,然后由于如果大的串出现了n次,那么小的串出现次数一定大于等于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 =250010;

  • const int maxv = maxn <<1;

  •  

  • struct node{

  •          int child[26], parent , maxlen ;

  •          node(  ){

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

  •                  parent = maxlen =0;

  •          }

  • } Node[ maxv ];

  •  

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

  •  

  • char s[ maxn ];

  • int n ;

  •  

  • void build(  ){

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

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

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

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

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

  •                           }

  •                  }

  •                  last = np ;

  •          }

  • }

  •  

  • struct edge{

  •          edge *next ;

  •          int t ;

  • }*head[ maxv ];

  •  

  • int d[ maxv ], sum[ maxv ], S[ maxv ], Top =0;

  •  

  • int ans[ maxn ];

  •  

  • void cal(  ){

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

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

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

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

  •          edge *p ;

  •          int i , j ;

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

  •                  for( j =0; j <26;++ j )if(C( i , 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 )){

  •                  ++ 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 <26;++ i )if(C( v , i )){

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

  •                  }

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

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

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

  •                           }

  •                  }

  •          }

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

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

  •                  ans[L( i )]=max( sum[ i ], ans[L( i )]);

  •          }

  •          for( i = n -1; i ;-- i ){

  •                  ans[ i ]=max( ans[ i ], ans[ i +1]);

  •          }

  • }

  •  

  • int main(  ){

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

  •          n =strlen( s +1);

  •          build(  );

  •          cal(  );

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

  •          return 0;

  • }



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

历史上的今天

评论

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

页脚

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