AK-dream

【题目描述】
很久很久以前,森林里住着一群跳蚤。一天,跳蚤国王得到了一个神秘的字符串,它想进行研究。首先,他会把串分成不超过 $k$ 个子串,然后对于每个子串 $S$,他会从$S$的所有子串中选择字典序最大的那一个,并在选出来的 $k$ 个子串中选择字典序最大的那一个。他称其为“魔力串”。现在他想找一个最优的分法让“魔力串”字典序最小。

【输入格式】
第一行一个整数 k, $k\leq 15$
接下来一个长度不超过 $10^5$ 的字符串 S。

【输出格式】
输出一行,表示字典序最小的“魔力串”。

题解

根据后缀数组height数组的定义,一个串s的本质不同的子串数目是$\sum_{i=2}^{|s|} |s|-sa[i]+1-height[i]$

可以二分答案$mid$,即判定字典序排名为第$mid$的子串是否可以作为答案

如何找到排在第$mid$的子串是哪一个?有个显而易见的结论:排在第i的后缀的所有前缀的字典序一定比 排在第i+1的后缀的所有前缀的字典序小
所以得到一个这样的求法

1
2
3
4
5
6
7
inline pair<int, int> getrnk(ll r) {
int i;
for (i = 1; i <= n && r > n - sa[i] - height[i] + 1; i++) {
r -= n - sa[i] - height[i] + 1;
}
return make_pair(sa[i], height[i] + r);
}

返回的是起始位置+子串长度 自行理解一下

然后其实二分判定是一个贪心的思想 从后往前扫 如果当前的这个后缀比二分的子串小了 就需要从上一位开始截掉 这个可以用LCP来快速判断

最后如果截断次数$<k$,就是一个符合条件的子串

时间复杂度$O(n\log n)$ (预处理ST表)

【代码】

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
#define N 100005
#define fi first
#define se second
using namespace std;
typedef long long ll;

char s[N];
int n, m, k, sa[N], sa2[N], rnk[N], key[N], sum[N], height[N];
int st[N<<1][21];

inline bool ok(int *num, int a, int b, int l) {
return num[a] == num[b] && num[a+l] == num[b+l];
}

inline void suffix() {
int i, j, p;
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[rnk[i]=s[i]]++;
for (i = 1; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[rnk[i]]--] = i;
for (j = 1; j <= n; j <<= 1, m = p) {
for (p = 0, i = n - j + 1; i <= n; i++) sa2[++p] = i;
for (i = 1; i <= n; i++) if (sa[i] > j) sa2[++p] = sa[i] - j;
for (i = 1; i <= n; i++) key[i] = rnk[sa2[i]];
for (i = 1; i <= m; i++) sum[i] = 0;
for (i = 1; i <= n; i++) sum[key[i]]++;
for (i = 1; i <= m; i++) sum[i] += sum[i-1];
for (i = n; i >= 1; i--) sa[sum[key[i]]--] = sa2[i];
for (swap(sa2, rnk), i = 2, p = 2, rnk[sa[1]] = 1; i <= n; i++) {
rnk[sa[i]] = ok(sa2, sa[i-1], sa[i], j) ? p-1 : p++;
}
}
}

inline void geth() {
int p = 0;
for (int i = 1; i <= n; i++) {
int j = sa[rnk[i]-1];
if (p) p--;
while (s[i+p] == s[j+p]) p++;
height[rnk[i]] = p;
}
}

inline void init_st() {
for (int i = 1; i <= n; i++) st[i][0] = height[i];
for (int l = 1; l <= 20; l++) {
for (int i = 1; i + (1 << l) - 1 <= n; i++) {
st[i][l] = min(st[i][l-1], st[i+(1<<(l-1))][l-1]);
}
}
}

inline int LCP(int x, int y) {
if (x == y) return n - x + 1;
int l = rnk[x], r = rnk[y];
if (l > r) swap(l, r);
l++;
int len = log2(r - l + 1);
return min(st[l][len], st[r-(1<<len)+1][len]);
}

inline pair<int, int> getrnk(ll r) {
int i;
for (i = 1; i <= n && r > n - sa[i] - height[i] + 1; i++) {
r -= n - sa[i] - height[i] + 1;
}
return make_pair(sa[i], height[i] + r);
}

inline bool cmp(pair<int, int> a, pair<int, int> b) {
int lcp = LCP(a.fi, b.fi);
if (lcp >= a.se || lcp >= b.se) {
return a.se <= b.se;
} else return s[a.fi + lcp] < s[b.fi + lcp];
}

inline bool check(ll mid) {
pair<int, int> a = getrnk(mid);
int cnt = 0;
for (int i = n, lst = n; i >= 1; i--) {
if (s[a.fi] < s[i]) {
return false;
}
if (!cmp(make_pair(i, lst - i + 1), a)) {
cnt++, lst = i;
}
if (cnt >= k) {
return false;
}
}
return true;
}

int main() {
scanf("%d%s", &k, s+1); n = strlen(s+1); m = 128;
suffix(); geth();
ll tot = 0;
for (int i = 1; i <= n; i++) tot += n - sa[i] + 1 - height[i];
init_st();
ll l = 1, r = tot, mid, ans = tot;
while (l <= r) {
mid = (l + r) >> 1;
if (check(mid)) {
ans = mid; r = mid - 1;
} else l = mid + 1;
}
pair<int, int> aa = getrnk(ans);
for (int i = aa.fi; i <= aa.fi + aa.se - 1; i++) {
putchar(s[i]);
}
return 0;
}


 评论