2014-04-19 19:13:00| 分类: oi,数据结构,spoj | 标签: |举报 |字号大中小 订阅
题目: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;
}
评论