题目链接: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的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
HDU图论题目分类
Hdu 1237 解题代码