xpycc's Blog

其实这题很早就想 AC 了。题目描述超短，做题思路也是比较清晰的：以 sa 的下标为结点和关键字，以区间内的 height 数组为优先级构造笛卡尔树，然后进行检索即可。我比较懒，直接就用 RMQ 来计算左右子树的分界点了，想 O(n) 构造笛卡尔树的话，可以用一个栈维护右链的方法得到。如果对这种构造方法不是很熟练的话，可以拿理工邀请赛的 F 题 (hdu 3410) 练下手。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 100000
#define MAXM 128			// 字母个数

int head[MAXN], succ[MAXN], succRank[MAXN];
int sa[MAXN], rank[MAXN];
int letter[MAXM];

void da(char* str, int len) {	// 倍增算法
	memset(letter, 0, sizeof(letter));
	for (int i = 0; i < len; ++i)
		if (!letter[str[i]])
			letter[str[i]] = 1;
	int total = -1;
	for (int i = 0; i < MAXM; ++i)
		if (letter[i])
			letter[i] = ++total;
	memset(head, 255, sizeof(head));
	for (int i = len - 1; i >= 0; --i) {	// 由于 head 头指针的性质，所以要倒序添加，下同
		rank[i] = letter[str[i]];
		succ[i] = head[rank[i]];
		head[rank[i]] = i;
	}
	int j = 0;
	for (int i = 0; i < len; ++i) {
		while (head[j] == -1) ++j;
		sa[i] = head[j];
		head[j] = succ[head[j]];
	}
	// 到此初始化排序完毕
	for (int k = 1; k < len; k <<= 1) {
		// 以下两个 for 对新一轮子串进行排序，由于第二关键字的排序在上一次排序中已完成
		// 故仅对第一关键字进行排序即可
		for (int i = len - 1; i >= 0; --i)		// 倒序添加
			if (sa[i] - k >= 0) {
				succRank[sa[i] - k] = rank[sa[i]];
				succ[sa[i] - k] = head[rank[sa[i] - k]];
				head[rank[sa[i] - k]] = sa[i] - k;
			}
		for (int i = len - 1; i >= len - k; --i) {	// 倒序添加
			succRank[i] = -1;					// 另外添加的尾字符的 rank 为 -1
			succ[i] = head[rank[i]];
			head[rank[i]] = i;
		}
		j = 0; total = -1;
		int preSuccRank = 0, preRank = 0;
		for (int i = 0; i < len; ++i) {
			while (head[j] == -1) ++j;
			sa[i] = head[j];
			if (i == 0 || preRank != rank[sa[i]] || preSuccRank != succRank[sa[i]]) {
				preRank = rank[sa[i]];
				rank[sa[i]] = ++total;	// 链表中保证不递减，所以可以这么做
			} else {
				preRank = rank[sa[i]];
				rank[sa[i]] = total;
			}
			preSuccRank = succRank[sa[i]];
			head[j] = succ[head[j]];
		}
	}
}

int height[MAXN];
long long mem[MAXN + 1], *sumLength = mem + 1;

void calcHeight(char* str, int len) {
	int i, j, k = 0;
	for (i = 0; i < len; ++i) {
		if (k != 0)				// h[i] >= h[i - 1] - 1
			--k;
		if (rank[i] == 0)
			continue;
		j = sa[rank[i] - 1];
		// 求 suffix(sa[rank[i] - 1]) 和 suffix(sa[rank[i]]) 的最大公共前缀
		while (str[i + k] == str[j + k])		// C 字符串以 '\0' 结尾
			++k;
		height[rank[i]] = k;	// h[i] = k;
	}
}

int minData[MAXN + 1][18];

inline int minHeight(int x, int y) {
	return height[x] <= height[y] ? x : y;
}

inline void initRMQ(int s, int e) {
	if (s > e)
		return;
	for (int i = s; i <= e; ++i)
		minData[i][0] = i;
	int h = (int)(log(e - s + 1.0) / log(2.0));
	for (int j = 1; j <= h; ++j)
		for (int i = s; i + (1 << j) - 1 <= e; ++i)
			minData[i][j] = minHeight(minData[i][j - 1], minData[i + (1 << (j - 1))][j - 1]);
}

inline int askRMQ(int a, int b) {
	int l = (int)(log(b - a + 1.0) / log(2.0));
	return minHeight(minData[a][l], minData[b - (1 << l) + 1][l]);
}

inline int lcp(int a, int b) {
	return height[askRMQ(std::min(rank[a], rank[b]) + 1, std::max(rank[a], rank[b]))];
}

char buf[MAXN + 2];
long long k;

int rk, rl;

void getAnswer(long long a, long long b) {
	int h = 0;
	while (a != b) {
		int idx = askRMQ(a + 1, b) - 1;
		if (k <= (height[idx + 1] - h) * (b - a + 1)) {
			rk = a; rl = h + 1 + (k - 1) / (b - a + 1);
			return;
		}
		k -= (height[idx + 1] - h) * (b - a + 1);
		if (k <= sumLength[idx] - sumLength[a - 1] - height[idx + 1] * (idx - a + 1)) {
			b = idx; h = height[idx + 1];
			continue;
		}
		k -= sumLength[idx] - sumLength[a - 1] - height[idx + 1] * (idx - a + 1);
		a = idx + 1;
		h = height[idx + 1];
	}
	rk = a; rl = h + k;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int test;
	scanf("%d", &test);
	for (int cas = 1; cas <= test; ++cas) {
		scanf("%s%I64d", buf, &k);
		int len = strlen(buf);
		da(buf, len);
		calcHeight(buf, len);

		for (int i = 0; i < len; ++i)
			sumLength[i] = sumLength[i - 1] + len - sa[i];
		initRMQ(1, len - 1);
		getAnswer(0, len - 1);

		printf("Case %d: ", cas);
		for (int i = 0; i < rl; ++i)
			putchar(buf[sa[rk] + i]);
		putchar('\n');
	}
	return 0;
}