K小子串 / 弦论

题目链接：ybt金牌导航2-3-3 / luogu P3975

题目大意

给你一个字符串，要你求字典序第 k 小的子串。
（相同的子串可能算一个，也可能算多个，数据以读入 0/1 来判断）

思路

考虑用 SAM 来做。

如果相同的子串算一个，那其实就是这一道题，直接看这道题的题解就可以了。
——>链接<——

接着我们来看如果相同的子串算多个怎么做。
那很明显就是要求出这个子串有多少个。
那我们可以通过 DP 来求。考虑到 $f{a}_i$ 的性质（后缀），我们可以用它的逆拓扑序顺序枚举点 $i$，然后 $f{a}_i$ 的个数加上它的个数，设求出的是 $siz{e}_i$。
（其实相同的子串算一个的话就其实就把 $siz{e}_i$ 都等于 $1$）

然后由于你有一些点是复制得到的，那那些点的 $size$ 初始化的时候就是 $0$，不是复制的初始化就是 $1$，不然你会一个加进去的字符可能会因此计算两次。

接着就跟之前一样 DP，求出 $i$ 出发每个子串的这个值的和。

然后就跟相同算一个时的做法一样了，直接用来比较的值变了。
而且你输出这个字符去找下一个的之后，原来我们只用减一，是因为相同的只算一个，但现在算多个了，那减去的就是 $siz{e}_i$。

然后就好了。

代码

#include<cstdio>
#include<cstring>
#define ll long long

using namespace std;

struct node {
	int len, fa, size;
	ll f, size_s;
	int son[31];
	node() {
		memset(son, 0, sizeof(son));
		len = fa = size = 0;
		f = -1ll;
		size_s = 0ll;
	}
}d[1000001];
int n, tot, lst, T, k;
int tong[1000001], xx[1000001];
char s[500001];

void SAM_build(int now) {
	int p = lst;
	int np = ++tot;
	d[np].len = d[p].len + 1;
	lst = np;
	d[np].size = 1;//新增点的大小是1
	
	for (; p && !d[p].son[now]; p = d[p].fa)
		d[p].son[now] = np;
	
	if (!p) d[np].fa = 1;
		else {
			int q = d[p].son[now];
			if (d[q].len == d[p].len + 1) d[np].fa = q;
				else {
					int nq = ++tot;
					d[nq] = d[q];
					d[nq].size = 0;//复制点的大小是0
					d[nq].len = d[p].len + 1;
					d[q].fa = nq;
					d[np].fa = nq;
					for (; p && d[p].son[now] == q; p = d[p].fa) {
						d[p].son[now] = nq;
					}
				}
		}
}

void dfs(int now) {
	if (d[now].f != -1) return ;
	d[now].f = 0;
	for (int i = 0; i < 26; i++)
		if (d[now].son[i]) {
			dfs(d[now].son[i]);
			d[now].f += d[d[now].son[i]].f;
		}
	d[now].f++;
}

void work(int now, int num) {
	while (num) {
		for (int i = 0; i < 26; i++)
			if (d[now].son[i]) {
				if (d[d[now].son[i]].f >= num) {
					putchar(i + 'a');
					now = d[now].son[i];
					num--;
					break;
				}
				else num -= d[d[now].son[i]].f;
			}
	}
}

void get_size() {
	for (int i = 0; i <= n; i++)//奇数排序按len从大到小排
		tong[i] = 0;
	for (int i = 1; i <= tot; i++)
		tong[d[i].len]++;
	for (int i = 1; i <= n; i++)
		tong[i] += tong[i - 1];
	for (int i = 1; i <= tot; i++)
		xx[tong[d[i].len]--] = i;
	
	for (int i = tot; i >= 1; i--) {
		d[d[xx[i]].fa].size += d[xx[i]].size;//转移得到 1 到 xx[i] 形成的子串的出现次数
	}
	
	d[1].size = 0;//DP 求出从前缀是 1 到 xx[i] 形成的串的有多少个子串
	for (int i = tot; i >= 1; i--) {
		d[xx[i]].size_s = d[xx[i]].size;
		for (int j = 0; j < 26; j++)
			if (d[xx[i]].son[j])
				d[xx[i]].size_s += d[d[xx[i]].son[j]].size_s;
	}
}

void work_s(int now, int num) {
	num -= d[1].size;
	while (num > 0) {
		for (int i = 0; i < 26; i++)
			if (d[now].son[i]) {
				if (d[d[now].son[i]].size_s >= num) {
					putchar(i + 'a');
					now = d[now].son[i];
					num -= d[now].size;//记得这里是减去它这个子串，之前只算一个只用减一，现在要减的就是这个子串的个数了
					break;
				}
				else num -= d[d[now].son[i]].size_s;
			}
	}
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	scanf("%d %d", &T, &k);
	
	tot = lst = 1;
	for (int i = 1; i <= n; i++)
		SAM_build(s[i] - 'a');
	
	dfs(1);
	
	if (!T) {
		if (k > d[1].f) {
			printf("-1");
			return 0;
		}
		work(1, k);
	}
	else {
		get_size();
		if (k > d[1].size_s) {
			printf("-1");
			return 0;
		}
		work_s(1, k);
	}
	
	return 0;
}