GreenCloudS

题目：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;

• }

•