SPOJ-7258. Lexicographical Subst

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

}