hdu 5030 Rabbit's String(后缀数组&二分)

Rabbit‘s String

Time Limit: 40000/20000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 288    Accepted Submission(s): 108

Problem Description

Long long ago, there lived a lot of rabbits in the forest. One day, the king of the rabbit kingdom got a mysterious string and he wanted to study this string.

At first, he would divide this string into no more than k substrings. Then for each substring S, he looked at all substrings of S, and selected the one which has the largest dictionary order. Among those substrings selected in the second round, the king then
choose one which has the largest dictionary order, and name it as a "magic string".

Now he wanted to figure out how to divide the string so that the dictionary order of that "magic string" is as small as possible.

Input

There are at most 36 test cases.

For each test case, the first line contains a integer k indicating the maximum number of substrings the king could divide, and the second line is the original mysterious string which consisted of only lower letters.

The length of the mysterious string is between 1 and 105 and k is between 1 and the length of the mysterious string, inclusive.

The input ends by k = 0.

Output

For each test case, output the magic string.

Sample Input

3
bbaa
2
ababa
0

Sample Output

b
ba

Hint

   For the first test case, the king may divide the string into "b", "b" and "aa".
   For the second test case, the king may divide the string into "aba" and "ba".

Source

2014 ACM/ICPC Asia Regional Guangzhou Online

Recommend

hujie   |   We have carefully selected several similar problems for you:  5053 5052 5051 5050 5049

题意:

给你一个长度不超过1e5的串。你最多可以把它切成k个连续的子串。然后对于切出来的子串拿出他们子串字典序最大的那个(子串的子串)。然后把所有拿出来的子串的子串字典序最大的那个串叫魔法串。现在要你输出字典序最小的魔法串。

思路:

最大中的最小。很容易想到二分(现在都是条件反射了)。首先我们求出sa,height。然后就可以求出f[i]即排名前i的后缀中有多少个不同的子串。然后我们二分魔法串的排名。通过排名我们可以借助f数组定位魔法串所属后缀的排名pos和魔法串的长度len。现在要解决的是怎么判断方案是否可行了。对于排名大于pos的后缀x如果tp=lcp(pos,x)=0肯定无解。不管怎么切都没用。否则我们可以在[sa[x],sa[x]+tp-1]选个位置切一刀。对于pos后的后缀都标记一次。然后贪心来切。看最少切多少刀。然后就可以判定了。

详细见代码:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
char txt[maxn];
int sa[maxn],T1[maxn],T2[maxn],ct[maxn],he[maxn],rk[maxn],n,m,cut;
int mk[maxn];
ll f[maxn],ans;
void getsa(char *st)
{
    int i,k,p,*x=T1,*y=T2;
    for(i=0; i<m; i++) ct[i]=0;
    for(i=0; i<n; i++) ct[x[i]=st[i]]++;
    for(i=1; i<m; i++) ct[i]+=ct[i-1];
    for(i=n-1; i>=0; i--)
        sa[--ct[x[i]]]=i;
    for(k=1,p=1; p<n; k<<=1,m=p)
    {
        for(p=0,i=n-k; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=k) y[p++]=sa[i]-k;
        for(i=0; i<m; i++) ct[i]=0;
        for(i=0; i<n; i++) ct[x[y[i]]]++;
        for(i=1; i<m; i++) ct[i]+=ct[i-1];
        for(i=n-1; i>=0; i--) sa[--ct[x[y[i]]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1; i<n; i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
    }
}
void gethe(char *st)
{
    int i,j,k=0;
    for(i=0;i<n;i++) rk[sa[i]]=i;
    for(i=0;i<n-1;i++)
    {
        if(k) k--;
        j=sa[rk[i]-1];
        while(st[i+k]==st[j+k]) k++;
        he[rk[i]]=k;
    }
}
bool isok(ll p)
{
    int pos,len,i,pp,cnt;
    pos=lower_bound(f+1,f+1+n,p)-f;//定位sa
    len=he[pos]+p-f[pos-1];//确定串长
    for(i=0;i<n;i++)
        mk[i]=-1;
    if(n-sa[pos]>len)//看自己所属后缀是否要切
        mk[sa[pos]]=sa[pos]+len-1;
    for(i=pos+1;i<=n;i++)
    {
        if(he[i]==0)
            return false;
        len=min(len,he[i]);//lcp
        mk[sa[i]]=sa[i]+len-1;//排序比pos大一定要分割。
    }
    pp=n,cnt=0;
    for(i=0;i<n;i++)
    {
        if(mk[i]!=-1)//能不切先不切和后面的一起切。贪心的思想。
            pp=min(pp,mk[i]);
        if(pp==i)
        {
            cnt++;
            if(cnt>cut)
                return false;
            pp=n;
        }
    }
    return cnt<cut;//切cnt次就是cnt+1块。
}
int main()
{
    int i,pos,len;
    ll low,hi,mid;

    while(scanf("%d",&cut),cut)
    {
        scanf("%s",txt);
        n=strlen(txt)+1;
        m=128;
        getsa(txt);
        gethe(txt);
        n--;
        f[1]=n-sa[1];
        for(i=2;i<=n;i++)
            f[i]=f[i-1]+n-sa[i]-he[i];
        low=1,hi=f[n],ans=1;
        while(low<=hi)
        {
            mid=(low+hi)>>1;
            if(isok(mid))
                ans=mid,hi=mid-1;
            else
                low=mid+1;
        }
        pos=lower_bound(f+1,f+1+n,ans)-f;
        len=he[pos]+ans-f[pos-1];
        txt[sa[pos]+len]=0;
        printf("%s\n",txt+sa[pos]);
    }
    return 0;
}

hdu 5030 Rabbit's String(后缀数组&二分)

时间: 09-29

hdu 5030 Rabbit's String(后缀数组&二分)的相关文章

hdu 5030 Rabbit&#39;s String(后缀数组)

题目链接:hdu 5030 Rabbit's String 题目大意:给定k和一个字符串,要求将字符串拆分成k个子串.然后将每个子串中字典序最大的子串选出来,组成一个包含k个字符串的集合,要求这个集合中字典序最大的字符串字典序最小. 解题思路:网赛的时候试图搞了一下这道题,不过水平还是有限啊,后缀数组也是初学,只会切一些水题.赛后看了一下别人的题解,把这题补上了. 首先对整个字符串做后缀数组,除了处理出sa,rank,height数组,还要处理处f数组,f[i]表示说以0~sa[i]开头共有多少

Hdu 5030 Rabbit&#39;s String (后缀数组)

题目大意: 要求将一个长串分解成最多k个子串,使得分开的n个串的字典序最大的那一个子串的字典序最小. 思路分析: 要最大的最小,不难想到二分的. 我们二分出原串中的第rk大子串就是目标串. 现在就是怎么判断这个串满足要求,也就是我们如何分其他部分,使之成为字典序最大的一个. 我们可以通过rk轻易的找到这是哪一个串,假设它处在sa[t]中. 那么可以知道 在 sa数组中t以前的子串的字典序都是比目标串小的. 而后面会有比sa大的,我们就要分解这些串. 我们从t 扫描 到n的height  ,如果有

HDU 5030 Rabbit&#39;s String

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5030 题意:给出一个长度为n的串S,将S分成最多K个子串S1,S2,……Sk(k<=K).选出每个子串Si(1<=i<=k)的最大子串SSi.最后使得k个SSi的最大值最小. 思路:首先用后缀数组求出所有子串.二分答案串,判定是否存在一种分法满足要求.对于答案串A,设A起始位置所组成的后缀排名为t,在排名为[t+1,n]的后缀中截取子串S[Li,Ri],使得Ri<n(下标1到n),且该

hdu 5008(2014 ACM/ICPC Asia Regional Xi&#39;an Online ) Boring String Problem(后缀数组&amp;二分)

Boring String Problem Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 219    Accepted Submission(s): 45 Problem Description In this problem, you are given a string s and q queries. For each que

hdu 3518 Boring counting(后缀数组)

Boring counting                                                                       Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Problem Description 035 now faced a tough problem,his english teacher gives him

BZOJ 3230: 相似子串( RMQ + 后缀数组 + 二分 )

二分查找求出k大串, 然后正反做后缀数组, RMQ求LCP, 时间复杂度O(NlogN+logN) --------------------------------------------------------------------- #include<cstdio> #include<algorithm> #include<cstring> #include<cctype> using namespace std; typedef long long

【bzoj4310】跳蚤 后缀数组+二分

题目描述 很久很久以前,森林里住着一群跳蚤.一天,跳蚤国王得到了一个神秘的字符串,它想进行研究. 首先,他会把串分成不超过 k 个子串,然后对于每个子串 S,他会从S的所有子串中选择字典序最大的那一个,并在选出来的 k 个子串中选择字典序最大的那一个.他称其为“魔力串”. 现在他想找一个最优的分法让“魔力串”字典序最小. 输入 第一行一个整数 k. 接下来一个长度不超过 105 的字符串 S. 输出 输出一行,表示字典序最小的“魔力串”. 样例输入 13 bcbcbacbbbbbabbacbcb

WHU---1084 - 连续技 (后缀数组+二分)

Description 不管是什么武功,多少都会有一或两个连续技多次出现,这些连续技常常是发明该武功的人的习惯性动作,如果这些动作被对手分析出来了,就很容易被对手把握住先机.比如松风剑谱里面有一式叫做迎风傲骨是如下的动作: 劈 刺 削 刺 削 踢 刺 削 刺 削 很明显 刺-削 这个连续动作出现了4次,而 刺-削-刺-削 这个连续动作则出现了两次. 现在刘白宇弄到了一本魔教的掌法,想让你帮忙来分析其中最长的且出现尽量多的连续技,当然,他不好意思麻烦你太久,只想让你告诉它这个连续技有多长并且出现了

poj 3261 Milk Patterns 后缀数组+二分

1 /*********************************************************** 2 题目: Milk Patterns(poj 3261) 3 链接: http://poj.org/problem?id=3261 4 题意: 给一串数字,求这些数字中公共子串个数大于k的 5 最长串. 6 算法: 后缀数组+二分 7 ***********************************************************/ 8 #incl