首页 > 代码库 > hdu 5030 Rabbit's String(后缀数组)
hdu 5030 Rabbit's String(后缀数组)
题目链接:hdu 5030 Rabbit‘s String
题目大意:给定k和一个字符串,要求将字符串拆分成k个子串。然后将每个子串中字典序最大的子串选出来,组成一个包含k个字符串的集合,要求这个集合中字典序最大的字符串字典序最小。
解题思路:网赛的时候试图搞了一下这道题,不过水平还是有限啊,后缀数组也是初学,只会切一些水题。赛后看了一下别人的题解,把这题补上了。
首先对整个字符串做后缀数组,除了处理出sa,rank,height数组,还要处理处f数组,f[i]表示说以0~sa[i]开头共有多少种不同的子串。然后在0到f[n]之间二分找答案。
判定的方法复杂度为o(n),计算在分割k-1次能否将比当前串字典序大的字符串变小。这里要借助height数组,判断至少要再哪里分割(注意LCA为0的话,直接就可以判定为false)。记录下每个分割的位置,再遍历一遍判定即可(因为有些分割的位置一下切割了不只一个串)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
struct Suffix_Arr {
char s[maxn];
int n, SA[maxn], rank[maxn], height[maxn];
int tmp_one[maxn], tmp_two[maxn], c[maxn];
ll f[maxn];
void init ();
void build(int m);
void get_height();
void solve ();
bool judge(ll m);
}AC;
int K;
int main () {
while (scanf("%d", &K) == 1 && K) {
AC.init();
AC.build(256);
AC.get_height();
AC.solve();
}
return 0;
}
bool Suffix_Arr::judge(ll m) {
int t = lower_bound(f + 1, f + n + 1, m) - f;
int R = n - (f[t] - m + 1);
int len = R - SA[t] + 1;
memset(c, -1, sizeof(c));
c[SA[t]] = len;
for (int i = t+1; i <= n; i++) {
len = min(len, height[i]);
if (len == 0)
return false;
c[SA[i]] = len;
}
int ret = 0, p = n + 1;
for (int i = 0; i < n; i++) {
if (i == p) {
ret++;
p = n + 1;
}
if (c[i] != -1)
p = min(p, i + c[i]);
if (ret >= K)
return false;
}
return true;
}
void Suffix_Arr::solve() {
ll l = 1, r = f[n];
for (int i = 0; i < 70; i++) {
ll mid = (l + r) / 2;
if (judge(mid))
r = mid;
else
l = mid;
}
int t = lower_bound(f + 1, f + n + 1, r) - f;
int len = n - (f[t] - r + 1);
for (int i = SA[t]; i <= len; i++)
printf("%c", s[i]);
printf("\n");
}
void Suffix_Arr::init() {
scanf("%s", s);
n = strlen(s) + 1;
}
void Suffix_Arr::get_height() {
for (int i = 0; i < n; i++)
rank[SA[i]] = i;
int mv = height[n-1] = 0;
for (int i = 0; i < n - 1; i++) {
if (mv) mv--;
int j = SA[rank[i] - 1];
while (s[i+mv] == s[j+mv])
mv++;
height[rank[i]] = mv;
}
n--;
f[0] = 0;
for (int i = 1; i <= n; i++)
f[i] = f[i-1] + n - SA[i] - height[i];
}
void Suffix_Arr::build(int m) {
int *x = tmp_one, *y = tmp_two;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n - 1; i >= 0; i--) SA[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1) {
int mv = 0;
for (int i = n - k; i < n; i++) y[mv++] = i;
for (int i = 0; i < n; i++) if (SA[i] >= k)
y[mv++] = SA[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < m; i++) c[i] += c[i-1];
for (int i = n - 1; i >= 0; i--) SA[--c[x[y[i]]]] = y[i];
swap(x, y);
mv = 1;
x[SA[0]] = 0;
for (int i = 1; i < n; i++)
x[SA[i]] = (y[SA[i-1]] == y[SA[i]] && y[SA[i-1] + k] == y[SA[i] + k] ? mv - 1 : mv++);
if (mv >= n)
break;
m = mv;
}
}
hdu 5030 Rabbit's String(后缀数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。