[TJOI2015]弦论(后缀自动机)

/*

一道在树上乱搞的题目

建立出parent树来， 然后就能搞出每个节点往后能扩展出几个串， 至于位置不同算同一个的话就强制让right集合大小为1即可

然后在树上类比权值线段树找第k大26分统计一下即可 

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

#include<iostream>

#define ll long long

#define mmp make_pair

#define M 1000100

using namespace std;

int read()

{

	int nm = 0, f = 1;

	char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;

	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';

	return nm * f;

}

int t, k;

char s[M];

int ch[M][26], sz[M], len[M], fa[M], tim[M], a[M], f[M], lst = 1, cnt = 1;

void insert(int c)

{

	int p = ++cnt, f = lst;

	lst = p;

	len[p] = len[f] + 1;

	sz[p] = 1;

	while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];

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

	else

	{

		int q = ch[f][c];

		if(len[q] == len[f] + 1) fa[p] = q;

		else

		{

			int nq = ++cnt;

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

			fa[nq] = fa[q];

			len[nq] = len[f] + 1;

			fa[q] = fa[p] = nq;

			while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];

		}

	}

}

void query(int now, int k)

{

	if(k <= sz[now]) return;

	k -= sz[now];

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

	{

		if(f[ch[now][i]] < k) k -= f[ch[now][i]];

		else

		{

			putchar('a' + i);

			query(ch[now][i], k);

			break;

		}

	}

}

int main()

{

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

	int l = strlen(s + 1);

	for(int i = 1; i <= l; i++) insert(s[i] - 'a');

	for(int i = 1; i <= cnt; i++) tim[len[i]]++;

	for(int i = 1; i <= cnt; i++) tim[i] += tim[i - 1];

	for(int i = 1; i <= cnt; i++) a[tim[len[i]]--] = i;

	for(int i = cnt; i >= 1; i--) sz[fa[a[i]]] += sz[a[i]];

	t = read(), k = read();

	if(t == 0) for(int i = 1; i <= cnt; i++) f[i] = sz[i] = 1;

	else for(int i = 1; i <= cnt; i++) f[i] = sz[i];

	f[1] = sz[1] = 0;

	for(int i = cnt; i >= 1; i--)

	{

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

		{

			f[a[i]] += f[ch[a[i]][j]];

		}

	}

	if(k > f[1]) return 0 * puts("-1");

	else query(1, k);

	return 0;

}
巴特西

[TJOI2015]弦论(后缀自动机)

最新文章

热门文章
