P3975 [TJOI2015]弦论

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 3k | 阅读时长 ≈ 3 分钟

P3975 [TJOI2015]弦论

传送门

洛谷

题目描述

为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?

输入输出格式

输入格式：

第一行是一个仅由小写英文字母构成的字符串s

第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同位置的相同子串算作多个。k的意义见题目描述。

输出格式：

输出数据仅有一行,该行有一个字符串,为第k小的子串。若子串数目不足k个,则输出-1。

输入输出样例

输入样例#1：

aabc
0 3

输出样例#1：

aab

输入样例#2：

aabc
1 3

输出样例#2：

aa

输入样例#3：

aabc
1 11

输出样例#3：

-1

说明

数据范围
对于$10\%$的数据，$n \le 1000$。

对于$50\%$的数据，$t = 0$。

对于$100\%$的数据，$n \le 5 × 10^5, t < 2, k \le 10^9$。

分析

T=0时，设$siz_i=1$，即出现次数设为1。
T=1时，将$siz_i$设为$Endpos$的大小，即出现次数。

之前在想如果复制的点不设置$siz_i$，最终统计时是否会出现$siz_i=0$的情况。
网上说不会。
那就自己yy一下。
因为复制的点一定有子树，而$siz_i$是子树中终止节点的个数。
那么我们就需要就证明子树中一定有至少一个终止节点。
因为它有子树，说明有终止节点(感觉像没证一样，但换个角度想想，我们又不傻，如果它的子树内没有终止节点，那么我们还建子树干嘛，只会平白浪费时间和空间)。
所以得证。
正确性不保证，自己什么都不懂，没有理论支持，自己yy自然没法保证正确性…
如果有人发现这个假了，或者有正确性保证的证明，请评论告诉我，谢谢。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500010
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int T,k,las=1,cnt=1,siz[maxn<<1],sum[maxn<<1],ch[maxn<<1][26],len[maxn<<1],fa[maxn<<1],tong[maxn<<1],ns[maxn<<1];
char str[maxn];
void add(int c)
{
	int p=las,np=las=++cnt;
	len[np]=len[p]+1;
	siz[cnt]=1;
	while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
	if(!p)fa[np]=1;
	else
	{
		int q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else
		{
			int nq=++cnt;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			len[nq]=len[p]+1;
			fa[q]=fa[np]=nq;
			while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p];
		}
	}
}
void pre()
{
	for(int i=1;i<=cnt;i++)tong[len[i]]++;
	for(int i=1;i<=cnt;i++)tong[i]+=tong[i-1];
	for(int i=1;i<=cnt;i++)ns[tong[len[i]]--]=i;
	for(int i=cnt;i>=1;i--)
		if(T)siz[fa[ns[i]]]+=siz[ns[i]];
		else siz[i]=1;
	siz[1]=0;
	for(int i=cnt;i>=1;i--)
	{
		sum[ns[i]]=siz[ns[i]];
		for(int j=0;j<26;j++)
			if(ch[ns[i]][j])
				sum[ns[i]]+=sum[ch[ns[i]][j]];
	}
}
void solve()
{
	if(k>sum[1])
	{
		puts("-1");
		return ;
	}
	int now=1;
	k-=siz[now];
	while(k)
	{
		int i=0;
		while(k>sum[ch[now][i]])
			k-=sum[ch[now][i]],i+=1;
		now=ch[now][i];
		putchar('a'+i);
		k-=siz[now];
	}
}
int main()
{
	scanf("%s",str);
	read(T,k);
	int len=strlen(str);
	for(int i=0;i<len;i++)add(str[i]-'a');
	pre();
	solve();
    return 0;
}