# 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

```#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(后缀数组&二分)

## 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

## 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