题目描述
Farmer John 打算带领 NN（1 \leq N \leq 5 \times 10^51≤N≤5×10
5
）头奶牛参加一年一度的”全美农场主大奖赛“。在这场比赛中，每个参赛者必须让他的奶牛排成一列，然后带领这些奶牛从裁判面前依此走过。
今年，竞赛委员会在接受报名时，采用了一种新的登记规则：取每头奶牛名字的首字母，按照它们在队伍中的次序排成一列。将所有队伍的名字按字典序升序排序，从而得到出场顺序。
FJ 由于事务繁忙，他希望能够尽早出场。因此他决定重排队列。
他的调整方式是这样的：每次，他从原队列的首端或尾端牵出一头奶牛，将她安排到新队列尾部。重复这一操作直到所有奶牛都插入新队列为止。
现在请你帮 FJ 算出按照上面这种方法能排出的字典序最小的队列。
输入格式
第一行一个整数 NN。
接下来 NN 行每行一个大写字母，表示初始队列。
输出格式
输出一个长度为 NN 的字符串，表示可能的最小字典序队列。
每输出 8080 个字母需要一个换行。
输入输出样例
输入 #1复制
6 A C D B C B
输出 #1复制
ABCBCD
题解：
样例分析：
ACDBCB
先出A，此时队列[A]
再出B，队列[AB]
再出C，队列[ABC]
再出B，队列[ABCB]
再出C，队列[ABCBC]
再出D，队列[ABCBCD]
此时不难看出贪心做，就直接比较原队列两端字母的大小，如果两端一样就再往里一位，直到出现大小关系。但是存在这样一个问题，如果原队列很长，前两边相等的很多，这样极易爆时，例如AA...ABCA....AA
我们可以用f[i]表示i开始的后缀，g[i]表示i开始的前缀（即把以i结尾的前缀倒过来），这样当str[L] == str[R]时，我们就可以直接比较f[L]与g[R]
数组f与g如何计算？暴力肯定不可取
我们可以将原队列翻转，就比如ACDBCB--->ACDBCB#BCBDCA，两者之间加一个其他字符（例如#，其实为什么加这个字符我也不是很清楚，貌似不加也可以过？？？）
因为我们将字符串倒过来，所以g是以i为开头的前缀其实就是后缀（数组g在翻转字符部分），懂没懂？也就是现在字符串分为前半部分为正序，后半部分为倒序，我们对正序取后缀，对倒序取前缀，其实本质都是取后缀，所以我们对新串进行后缀数组，
f[i]就是rank[i],g[i]就是rank[2(n+1)-i]
(Rank[i]=后缀suf(i)的排名, suf(k)为s(k…n)构成的子串)
比如acabca，处理完就是acabca#acbaca
比较两个c的时候，其实就是比较第一个c的排名和倒数第二个c的排名
代码：
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
char str[N];
string ans;
int n, m, sa[N], rk[N], oldrk[N<<1], pos[N], cnt[N],id[N],px[N];
bool cmp(int x, int y, int k)
{
return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}
void getsa()
{
m = 122;int i,w,p;
for (i = 1; i <= n; ++i) ++cnt[rk[i] = str[i]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;
for (w = 1; w < n; w <<= 1, m = p) { // m=p 就是优化计数排序值域
for (p = 0, i = n; i > n - w; --i) id[++p] = i;
for (i = 1; i <= n; ++i)
if (sa[i] > w) id[++p] = sa[i] - w;
memset(cnt, 0, sizeof(cnt));
for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];
memcpy(oldrk, rk, sizeof(rk));
for (p = 0, i = 1; i <= n; ++i)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
getchar();
scanf("%c",&str[i]);
}
str[n+1]='0';
for(int i=n+2;i<=n*2+1;i++)
str[i]=str[2*n-i+2];
n=n*2+1;
getsa();
int l=1,r=n/2;
while(l<=r)
{
if(str[l]<str[r]) ans+=str[l++];
else if(str[l]>str[r]) ans+=str[r--];
else
{
if(rk[l]<rk[n/2+n/2-r+2]) ans+=str[l++];
else ans+=str[r--];
}
}
for(int i=0;i<ans.size();i++)
{
printf("%c",ans[i]);
if((i+1)%80==0) printf("\n");
}
return 0;
} #include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
char str[N];
string ans;
int n, m, sa[N], rk[N], oldrk[N<<1], pos[N], cnt[N];
bool cmp(int x, int y, int k)
{
return oldrk[x] == oldrk[y] && oldrk[x + k] == oldrk[y + k];
}
void getsa()
{
m = 122;
for (int i = 1; i <= n; i++)
++cnt[rk[i] = str[i]];
for (int i = 1; i <= m; i++)
cnt[i] += cnt[i - 1];
for (int i = n; i; i--)
sa[cnt[rk[i]]--] = i;
for (int k = 1; k <= n; k <<= 1)
{
int num = 0;
for (int i = n - k + 1; i <= n; i++)
pos[++num] = i;
for (int i = 1; i <= n; i++)
{
if (sa[i] > k)
pos[++num] = sa[i] - k;
}
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)
++cnt[rk[i]];
for(int i=1;i<=m;i++)
cnt[i]+=cnt[i-1];
for (int i = n; i; i--)
sa[cnt[rk[pos[i]]]--] = pos[i];
num = 0;
memcpy(oldrk, rk, sizeof(rk));
for (int i = 1; i <= n; i++)
rk[sa[i]]=cmp(sa[i],sa[i-1],k)?num:++num;
if(num==n) break;
m=num;
}
for(int i=1;i<=n;i++)
rk[sa[i]]=i;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
getchar();
scanf("%c",&str[i]);
}
str[n+1]='0';
for(int i=n+2;i<=n*2+1;i++)
str[i]=str[2*n-i+2];
n=n*2+1;
getsa();
int l=1,r=n/2;
while(l<=r)
{
if(str[l]<str[r]) ans+=str[l++];
else if(str[l]>str[r]) ans+=str[r--];
else
{
if(rk[l]<rk[n/2+n/2-r+2]) ans+=str[l++];
else ans+=str[r--];
}
}
for(int i=0;i<ans.size();i++)
{
printf("%c",ans[i]);
if((i+1)%80==0) printf("\n");
}
return 0;
} 
京公网安备 11010502036488号