自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 22:47:33，当前版本为作者最后更新于2023-05-15 21:53:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 首先考虑仅执行前两种操作可以得到的最小字符串。

一个显然的贪心是，若当前 $S$ 的首字符大于 $T$ 的首字符就执行第二个操作，否则执行第一个操作。不难证明其正确性。

• 回到原问题。

先将题意转化为：将 $S$ 分成前后两个部分 $A,B$，对 $A$ 从左到右执行前两种操作，对 $B$ 从右到左执行第三种操作。令对 $A$ 执行第一种操作在 $T$ 中形成的字符串为 $C$，对 $A$ 执行第二种操作在 $T$ 中形成的字符串为 $D$。

我们可以将第三种操作视作将 $B$ 不改变顺序地穿插到 $C$ 中的任意位置，即形成一个字符串 $E$，使得 $E$ 能够恰好划分为两个分别与 $B,C$ 相同的子序列。最终 $T$ 即为 $E+D$，其中 $+$ 表示字符串的拼接。

以第二个样例中 $S=\mathsf{{\color{orange}d}{\color{orange}c}{\color{orange}b}{\color{yellowgreen}c}{\color{orange}a}{\color{yellowgreen}d}{\color{cornflowerblue}b}}$ 构造出 $T=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}{\color{yellowgreen}c}{\color{yellowgreen}d}}$ 为例，将 $S$ 分为前后两个部分 $A=\mathsf{{\color{orange}d}{\color{orange}c}{\color{orange}b}{\color{yellowgreen}c}{\color{orange}a}{\color{yellowgreen}d}},B=\mathsf{{\color{cornflowerblue}b}}$，对橙色部分执行第一种操作，对绿色部分执行第二种操作，得到 $C=\mathsf{{\color{orange}a}{\color{orange}b}{\color{orange}c}{\color{orange}d}},D=\mathsf{{\color{yellowgreen}c}{\color{yellowgreen}d}}$，再将 $B$ 插入 $C$ 中得到 $E=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}}$，最终 $T=E+D=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}{\color{yellowgreen}c}{\color{yellowgreen}d}}$。

观察整个 $T$ 的构造流程，我们接下来需要解决三个问题：

1. 若确定了 $A$，如何构造最优的 $C,D$？
2. 若确定了 $B,C$，如何构造最优的 $E$？
3. 如何划分 $A,B$？

对于第一个问题，我们一开始已经解决了。形式化地来讲，我们对 $A$ 中所有前缀最小字符进行第一种操作，对剩余字符进行第二种操作，其中前缀最小字符指的是不大于自身之前任意字符的字符。可以观察到，这样形成的 $C$ 一定是个单调不降的字符序列。

对于第二个问题，由于 $C$ 中字符单调不降，故我们依然可以采取一个贪心的策略：若 $B$ 的首字符大于 $C$ 的首字符，则将 $C$ 的首字符加入到 $E$ 的末尾并将 $C$ 的首字符删去，否则将 $B$ 的首字符加入到 $E$ 的末尾并将 $B$ 的首字符删去。

对于第三个问题，暴力枚举 $A,B$ 的划分位置。

按照上述过程模拟，我们便得到了一个 $O(n^2)$ 的做法。

• 考虑优化。

瓶颈在于枚举 $A,B$ 的划分位置上，考虑能否缩小枚举范围。

不难发现，对 $S$ 中所有前缀最小字符均进行第一种操作一定不劣。也就是说，令 $S$ 中最小字符的最后出现位置为 $p$，则将 $S_p$ 及其之前的字符都归到 $A$ 中一定不劣。那么此时整个 $C$ 和 $D$ 的一段前缀就确定下来了。

令 $S$ 中 $S_{p+1}$ 记其之后的字符构成的字符串为 $X$，则我们需要选取 $X$ 的一个后缀作为 $B$，剩余部分就接在已经确定的 $D$ 的后面。既然 $B$ 最终在 $D$ 前，那么我们希望选出来的 $B$ 的字典序尽可能小。一个自然的想法是直接选取 $X$ 的最小后缀作为 $B$，但很可惜这是错的。一个简单的反例是 $S=\mathsf{{\color{orange}c}{\color{orange}b}{\color{yellowgreen}d}{\color{orange}a}{\color{cornflowerblue}b}{\color{cornflowerblue}c}{\color{cornflowerblue}b}}$，此时最优的 $B$ 应当是 $\mathsf{{\color{cornflowerblue}b}{\color{cornflowerblue}c}{\color{cornflowerblue}b}}$，而不是字典序最小的 $\mathsf{{\color{cornflowerblue}b}}$。

那么问题出在哪儿呢？出在 “字典序最小” 的条件中包含了对于字符串长度的比较。对于 $X$ 的两个后缀 $s,s'\ (|s|<|s'|)$，若 $\forall 1\le i\le |s|$ 都有 $s_i=s'_i$，那么虽然 $s$ 字典序比 $s'$ 小，但若后面加上了 $D$，$s'$ 却可能比 $s$ 更优。

我们退而求其次，选择 $X$ 中不考虑长度限制的字典序最小的若干后缀。但这样的字符串可能仍旧很多，无法直接模拟。

观察这些后缀的性质。令这些后缀分别为 $s_1,s_2,\dots,s_k\ (|s_1|<|s_2|<\dots<|s_k|)$，那么 $\forall 1\le i<k$ 都有 $s_i$ 为 $s_{i+1}$ 的一段前缀，即 $s_i$ 为 $s_{i+1}$ 的一个 border，亦即 $s_2,s_3,\dots,s_k$ 为 $s_1$ 的 border。

接下来有两条路可走。

法一

依据这个性质，我们可以利用 $s_i$ 的结果推出 $s_{i+1}$ 的结果。具体地，要想比较 $B=s_i$ 所构造出的 $T$ 和 $B=s_{i+1}$ 所构造出的 $T'$ 的大小，我们可以在 $T$ 的基础上，根据前文的贪心，暴力添加字符直至 $B=s_{i+1}$。在添加的过程中进行逐位比较，添加完成后，由于剩余的部分构成一段区间，那么直接利用你喜欢的方式比较即可。

时间复杂度瓶颈在于后缀排序。

#include<bits/stdc++.h>
using namespace std;
int t,n,nc,nd,ns,tp,sa[1000009],rnk[1000009],slen[1000009];
char s[1000009],C[1000009],D[1000009],T[1000009],ans[1000009];
inline int read(){
	int s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
namespace SAM{
	int tp,tot,cnt = 1,last = 1,tmp[26],hd[2000009],fa[2000009],dy[2000009],id[2000009],len[2000009],pos[2000009],suf[2000009],ch[2000009][26];
	struct st{int x,y;}eg[2000009];
	void addedge(int u,int v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
	void clear(){
		for (int i = 1;i <= cnt;i += 1){
			memset(ch[i],0,sizeof(ch[i]));
			fa[i] = dy[i] = id[i] = len[i] = pos[i] = suf[i] = 0;
		}
		cnt = last = 1;
	}
	void ins(int x,int y){
		int p = last,cur = ++ cnt;
		pos[cur] = y,suf[cur] = 1,len[cur] = len[last] + 1;
		while (p && !ch[p][x]) ch[p][x] = cur,p = fa[p];
		int q = ch[p][x];
		if (!q) fa[cur] = 1;
		else if (len[p] + 1 == len[q]) fa[cur] = q;
		else{
			int r = ++ cnt;
			fa[r] = fa[q],pos[r] = pos[q],len[r] = len[p] + 1;
			memcpy(ch[r],ch[q],sizeof(ch[q]));
			while (p && ch[p][x] == q) ch[p][x] = r,p = fa[p];
			fa[cur] = fa[q] = r;
		}
		last = cur;
	}
	void dfs(int u,bool fl,bool opt){
		if (suf[u]){
			if (opt){
				if (!fl) return;
				slen[++ ns] = n - pos[u] + 1;
			}
			else tp += 1,sa[tp] = pos[u],rnk[pos[u]] = tp;
		}
		for (int i = hd[u];i;i = eg[i].y) dfs(eg[i].x,fl,opt),fl = 0;
	}
	void work(int opt){
		tp = tot = 0;
		for (int i = 0;i < 26;i += 1) tmp[i] = 0;
		for (int i = 1;i <= cnt;i += 1) hd[i] = 0;
		for (int i = 1;i <= cnt;i += 1) dy[i] = T[pos[i] + len[fa[i]]] - 'a',tmp[dy[i]] += 1;
		for (int i = 1;i < 26;i += 1) tmp[i] += tmp[i - 1];
		for (int i = 1;i <= cnt;i += 1) id[tmp[dy[i]] --] = i;
		for (int i = cnt;i >= 1;i -= 1) if (fa[id[i]]) addedge(fa[id[i]],id[i]);
		dfs(1,1,opt);
	}
}
void clear(){
	SAM :: clear();
	nc = nd = ns = tp = 0;
	for (int i = 1;i <= n;i += 1) sa[i] = rnk[i] = slen[i] = 0;
}
int main(){
	t = read();
	while (t --){
		clear(),scanf("%s",s + 1),n = strlen(s + 1);
		int pos = 1;
		for (int i = 1;i <= n;i += 1) if (s[i] <= s[pos]){
			C[++ nc] = s[i];
			for (int j = pos + 1;j < i;j += 1) D[++ nd] = s[j];
			pos = i;
		}
		reverse(C + 1,C + nc + 1);
		for (int i = 1;i <= nc;i += 1) T[i] = C[i];
		for (int i = 1;i <= nd;i += 1) T[i + nc] = D[i];
		for (int i = pos + 1;i <= n;i += 1) T[i] = s[i];
		for (int i = n;i > pos;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(1);
		for (int i = pos;i >= 1;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(0);
		int fl = 0,res = 0,now = 1,cur = 1,cpos = 1,mnpos = n - slen[ns];
		for (int i = 1;i <= slen[ns];i += 1){
			while (cpos <= nc && T[cpos] < T[mnpos + i]){
				if (!fl && T[cpos] < T[cur]) fl = 1;
				if (!fl && T[cpos] > T[cur]) goto GG;
				cur += 1,cpos += 1;
			}
			if (!fl && T[mnpos + i] < T[cur]) fl = 1;
			if (!fl && T[mnpos + i] > T[cur]) goto GG;
			cur += 1;
			if (i == slen[now]){
				if (fl == 1 || rnk[cpos] < rnk[cur]) cur = cpos,res = slen[now];
				fl = 0,now += 1;
			}
		}
		GG:;
		cpos = 1;
		for (int i = 1;i <= res;i += 1){
			while (cpos <= nc && T[cpos] < T[mnpos + i]) ans[++ tp] = T[cpos ++];
			ans[++ tp] = T[mnpos + i];
		}
		while (cpos <= nc) ans[++ tp] = T[cpos ++];
		for (int i = 1;i <= nd;i += 1) ans[++ tp] = T[nc + i];
		for (int i = pos + 1;i <= n - res;i += 1) ans[++ tp] = T[i];
		for (int i = 1;i <= n;i += 1) putchar(ans[i]);
		puts("");
	}
	return 0;
}

法二

根据 border 的性质，我们可将 $|s_1|,|s_2|,\dots,|s_k|$ 分成 $O(\log k)$ 段等差数列。记有 $c$ 段等差数列，第 $i$ 段由 $s_{l_i},s_{l_i+1},\dots,s_{r_i}$ 构成。

可以根据调整法证明，最优的 $B$ 一定只存在于每段的首两项和末一项，即 $s_{l_i},s_{l_i+1},s_{r_i}$ 之中。枚举这些位置直接模拟即可。

时间复杂度为 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
int t,n,fl,nc,nd,ns,tp,sa[1000009],rnk[1000009],ban[1000009],slen[1000009];
char s[1000009],C[1000009],D[1000009],T[1000009],ans[1000009];
inline int read(){
	int s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
namespace SAM{
	int tp,tot,cnt = 1,last = 1,tmp[26],hd[2000009],fa[2000009],dy[2000009],id[2000009],len[2000009],pos[2000009],suf[2000009],ch[2000009][26];
	struct st{int x,y;}eg[2000009];
	void addedge(int u,int v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
	void clear(){
		for (int i = 1;i <= cnt;i += 1){
			memset(ch[i],0,sizeof(ch[i]));
			fa[i] = dy[i] = id[i] = len[i] = pos[i] = suf[i] = 0;
		}
		cnt = last = 1;
	}
	void ins(int x,int y){
		int p = last,cur = ++ cnt;
		pos[cur] = y,suf[cur] = 1,len[cur] = len[last] + 1;
		while (p && !ch[p][x]) ch[p][x] = cur,p = fa[p];
		int q = ch[p][x];
		if (!q) fa[cur] = 1;
		else if (len[p] + 1 == len[q]) fa[cur] = q;
		else{
			int r = ++ cnt;
			fa[r] = fa[q],pos[r] = pos[q],len[r] = len[p] + 1;
			memcpy(ch[r],ch[q],sizeof(ch[q]));
			while (p && ch[p][x] == q) ch[p][x] = r,p = fa[p];
			fa[cur] = fa[q] = r;
		}
		last = cur;
	}
	void dfs(int u,bool fl,bool opt){
		if (suf[u]){
			if (opt){
				if (!fl) return;
				slen[++ ns] = n - pos[u] + 1;
			}
			else tp += 1,sa[tp] = pos[u],rnk[pos[u]] = tp;
		}
		for (int i = hd[u];i;i = eg[i].y) dfs(eg[i].x,fl,opt),fl = 0;
	}
	void work(int opt){
		tp = tot = 0;
		for (int i = 0;i < 26;i += 1) tmp[i] = 0;
		for (int i = 1;i <= cnt;i += 1) hd[i] = 0;
		for (int i = 1;i <= cnt;i += 1) dy[i] = T[pos[i] + len[fa[i]]] - 'a',tmp[dy[i]] += 1;
		for (int i = 1;i < 26;i += 1) tmp[i] += tmp[i - 1];
		for (int i = 1;i <= cnt;i += 1) id[tmp[dy[i]] --] = i;
		for (int i = cnt;i >= 1;i -= 1) if (fa[id[i]]) addedge(fa[id[i]],id[i]);
		dfs(1,1,opt);
	}
}
void upd(){
	for (int i = 1;i <= n;i += 1){
		if (ans[i] < T[i]) return;
		if (ans[i] > T[i]){
			for (int j = 1;j <= n;j += 1) ans[j] = T[j];
			return;
		}
	}
}
void simulate(int o){
	int nc = 0,nd = 0,pos = 1;
	for (int i = 1;i <= o;i += 1){
		if (s[i] <= s[pos]) C[++ nc] = s[i],pos = i;
		else D[++ nd] = s[i];
	}
	reverse(C + 1,C + nc + 1);
	int tp = 0,cpos = 1;
	for (int i = o + 1;i <= n;i += 1){
		while (cpos <= nc && C[cpos] < s[i]) T[++ tp] = C[cpos ++];
		T[++ tp] = s[i];
	}
	while (cpos <= nc) T[++ tp] = C[cpos ++];
	for (int i = 1;i <= nd;i += 1) T[++ tp] = D[i];
	if (!fl) for (int i = 1;i <= n;i += 1) ans[i] = T[i];
	else upd();
	fl = 1;
}
void clear(){
	SAM :: clear();
	fl = nc = nd = ns = tp = 0;
	for (int i = 1;i <= n;i += 1) sa[i] = rnk[i] = ban[i] = slen[i] = 0;
}
int main(){
	t = read();
	while (t --){
		clear(),scanf("%s",s + 1),n = strlen(s + 1);
		int pos = 1;
		for (int i = 1;i <= n;i += 1) if (s[i] <= s[pos]){
			C[++ nc] = s[i];
			for (int j = pos + 1;j < i;j += 1) D[++ nd] = s[j];
			pos = i;
		}
		reverse(C + 1,C + nc + 1);
		for (int i = 1;i <= nc;i += 1) T[i] = C[i];
		for (int i = 1;i <= nd;i += 1) T[i + nc] = D[i];
		for (int i = pos + 1;i <= n;i += 1) T[i] = s[i];
		for (int i = n;i > pos;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(1);
		for (int i = pos;i >= 1;i -= 1) SAM :: ins(T[i] - 'a',i);
		SAM :: work(0);
		for (int i = 2;i < ns;i += 1) if (slen[i] - slen[i - 1] == slen[i + 1] - slen[i]) ban[i] = 1;
		for (int i = 0;i <= ns;i += 1){
			if (i <= 1 || i == ns || !ban[i - 1] || !ban[i]) simulate(n - slen[i]);
		}
		for (int i = 1;i <= n;i += 1) putchar(ans[i]);
		puts("");
	}
	return 0;
}