【bzoj3998】[TJOI2015]弦论

题目描述：

对于一个给定长度为N的字符串，求它的第K小子串是什么。

样例输入：

aabc
0 3

样例输出：

aab

题解：

构造后缀自动机，然后在后缀自动机上跑dfs

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#ifdef WIN32

	#define LL "%I64d"

#else

	#define LL "%lld"

#endif

#ifdef CT

	#define debug(...) printf(__VA_ARGS__)

#else

	#define debug(...)

#endif

#define R register

#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)

#define gmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))

#define gmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))

#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)

#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)

char B[1<<15],*S=B,*T=B;

inline int FastIn()

{

	R char ch;R int cnt=0;R bool minus=0;

	while (ch=getc(),(ch < '0' || ch > '9') && ch != '-') ;

	ch == '-' ?minus=1:cnt=ch-'0';

	while (ch=getc(),ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';

	return minus?-cnt:cnt;

}

#define maxn 1000010

char str[maxn];

int a[maxn][26] , val[maxn] , fa[maxn] , l[maxn] ,last , tot , p , np , q , nq , t , k ;

int v[maxn] , que[maxn] , sum[maxn] ;

inline void extend (R int c)

{

	p = last ;

	np = last = ++tot ;

	l[np] = l[p] + 1 ;

	val[np] = 1;

	for ( ; !a[p][c] && p ; ) a[p][c] = np , p = fa[p] ;

	if (!p) fa[np] = 1 ;

	else

	{

		q = a[p][c] ;

		if (l[p] + 1 == l[q] ) fa[np] = q ;

		else

		{

			nq = ++tot ;

			l[nq] = l[p] + 1 ;

			memcpy ( a[nq] , a[q] ,sizeof (a[q]) );

			fa[nq] = fa[q] ;

			fa[np] = fa[q] = nq ;

			for ( ; a[p][c]==q ; ) a[p][c] = nq , p = fa[p] ;

		}

	}

}

inline void prepare()

{

	for (R int i = 1 ; i <= tot ; i++ ) v[ l[i] ] ++ ;

	for (R int i = 1 ; str[i] ; i++ ) v[i] += v[i-1] ;

	for (R int i = tot ; i ; i-- ) que [ v[ l[i] ] -- ] = i ;

	for (R int i = tot ; i ; i-- )

	{

		R int tmp = que[i];

		if (t == 1) val[fa[tmp]] += val[tmp] ;

		else val[tmp] = 1 ;

	}

	val[1] = 0 ;

	for (R int i = tot ; i ; i--)

	{

		R int tmp = que[i] ;

		sum[tmp] = val[tmp] ;

		for (R int j = 0 ; j < 26 ; j++ )

			sum[tmp] += sum [ a[tmp][j] ] ;

	}

}

void dfs(R int x , R int k)

{

	if (k <= val [x] ) return ;

	k -= val[x] ;

	for (R int i = 0 ; i < 26 ; i++ )

	{

		if (int tmp = a[x][i] )

		{

			if (k <= sum[tmp] )

			{

				printf("%c" , i + 'a' );

				dfs(tmp , k);

				return ;

			}

			k -= sum[tmp];

		}

	}

}

int main()

{

	last = ++ tot;

	scanf ( "%s\n", str + 1);

	scanf( "%d %d" , &t , &k);

	for (R int i = 1 ; str[i] ; i++) extend( str[i] - 'a');

	prepare();

	if ( sum[1] < k) puts("-1") ;

	else dfs(1 , k ) ;

	return 0;

}

/*

aasdfsdafsdafsadfasdfsadf

0 4

aasd

*/

巴特西

【bzoj3998】[TJOI2015]弦论

最新文章

热门文章