自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 22:09:40，当前版本为作者最后更新于2021-03-11 19:44:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

使用 Lyndon word 相关理论可以导出本题的一个简洁线性做法

zx 哥哥的线性做法，然而我并没有看懂.

首先考虑如果给定一个串 $s$，那么什么样的位置可能是最小表示

对 $s$ 做 Lyndon 分解，合并相同的 Lyndon word，会得到 $s=w_1^{k_1}w_2^{k_2}\cdots w_m^{k_m}$，其中 $w_1>w_2>\cdots>w_m$

首先显然选择的位置一定是 Lyndon word 的开头，接下来我们断言如果选择了 $w_i^kw_{i+1}^{k_{i+1}}\cdots w_m^{k_m}$，那么 $k=k_i$.

证明：只需比较 $u^2v,uv,v$ 的大小. 如果 $u\geq v$，那么自然有 $u^2v>uv>v$；否则，如果 $u$ 不是 $v$ 的前缀，那么有 $u^2v<uv<v$；如果 $u$ 是 $v$ 的前缀，那么我们可以把 $v$ 不断去掉前缀 $v$ 来变成之前的情况，从而 $uv$ 总是不优的. 注意这个证明并没有使用 Lyndon word 的任何性质，这对一般的字符串也是成立的.

注意到一个性质：如果 $u,v$ 是任意串，$w$ 是 Lyndon word，$u<w,v<w$，那么 $uv<w$

设 $S_i=w_i^{k_i}w_{i+1}^{k_{i+1}}\cdots w_m^{k_m}$. 由于 $w_i>w_{i+1}$ 且 $w_i$ 是 Lyndon word，容易推出 $w_i^{k_i}\geq w_i>S_{i+1}$. 首先 $S_m$ 可能是一个最小表示的开始，接下来如果 $S_m$ 不是 $w_{m-1}$ 的前缀那么所有 $i<m$ 的 $S_i$ 都无法成为最小表示. 如果是前缀，那么再考虑如果 $S_{m-1}$ 不是 $w_{m-2}$ 的前缀，则所有 $i<m-1$ 的 $S_i$ 都无法成为最小表示. 以此类推，我们能找到一个最小的 $i$，满足 $\forall i\leq k<m$ 有 $S_{k+1}$ 是 $w_k$ 的前缀. 只有这些 $i\leq k\leq m$ 的 $S_k$ 可能成为最小表示.

注意到这已经导出了一个 $O(n\log n)$ 做法：$i$ 每减小 $1$ 后缀长度至少乘二，因此可行的 $i$ 只有 $O(\log n)$ 个. 我们维护每个前缀的 Lyndon 分解（用单调栈维护当前所有 Lyndon word（形如 $[l_i,r_i]$），每次插入一个 $[i,i]$，如果栈顶元素小于加入的 Lyndon word 就将其合并，否则就得到了最后一个 Lyndon word），暴力向前枚举上面所说的后缀即可.

但我们不满足于此. 还是来考虑 Duval 算法，设当前考虑到的字符串为 $s=u^ku'$，其中 $u'$ 是 $u$ 的可空真前缀，$u$ 是 Lyndon word. 在运行过程中同时维护每个原串前缀的最小表示的起始位置，设为 $ans_i$. 考虑加入一个字符 $c$ 造成的影响. 我们首先给出结论，然后给出证明. 设 $c$ 的位置为 $i$ 且之前未被更新过，那么

• 如果 $s_{|u'|+1}=c$，那么 $ans_i$ 为 $i-(|u|-ans_{|u'|+1})$ 和 $1$ 中更优的那个
• 如果 $s_{|u'|+1}<c$，那么 $ans_i=1$
• 如果 $s_{|u'|+1}>c$，那么等到以后再更新.

考虑其正确性，我们在什么时候会进行新的一轮遍历？答案是末尾的 $u'$ 严格小于（指非前缀）$u$ 的时候. 对于这个字符以后的前缀而言，根据我们上面的理论，$u$ 将不可能成为其最小表示. 所以，对于每一轮循环，$u$ 前面的字符串将不再有贡献，有贡献的只有 $u'$ 中的位置和第一个 $u$ 的起始位置. 如果选择 $u'$ 中的位置，那么我们发现这些位置开始的循环表示其实就是第一个 $u$ 中的 $u'$ 在当时的循环表示后面填上 $u^k$，于是答案是一样的. 注意这必须保证对应位置的 $ans$ 在当前考虑的串中才成立，当然如果不在那么必然更劣.

现在我们只需要解决比较两个子串. 注意由于我们上面的理论，其中一个必然是另一个的后缀，于是只需要求一个后缀和原串的 lcp，可以用 exkmp 线性求出.

IO 时间差不多占了一半

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=3e6+500;
char st[N];
int n;
int lcp[N];
int ans[N];
int chkmin(int x,int y,int r)
{
	if(x==y)return x;
	int len=lcp[x+r-y+1];//cout<<len<<endl;
	if(len<y-x)return st[x+r-y+1+len]<st[len+1]?x:y;
	len=lcp[y-x+1];
	if(len>=x-1)return x;
	else return st[len+1]<st[y-x+1+len]?x:y;
}
void exkmp()
{
	lcp[1]=n;int mid=2,r=0;
	for(int i=2;i<=n;i++)
	{
		if(i<=r)lcp[i]=min(lcp[i-mid+1],r-i+1);
		else lcp[i]=0;
		while(i+lcp[i]<=n&&st[1+lcp[i]]==st[i+lcp[i]])++lcp[i];
		if(mid+lcp[i]-1>=r)mid=i,r=mid+lcp[i]-1;
	}
//	for(int i=1;i<=n;i++)cout<<lcp[i]<<" ";puts("");
}
char obuf[1<<25],*oh=obuf;
inline void out(int x){
	if(!x){*oh++='0';return;}
	static int buf[30];int xb=0;
	for(;x;x/=10)buf[++xb]=x%10;
	for(;xb;)*oh++=buf[xb--]|48;	
}
int main()
{
	n=fread(st+1,1,N-500,stdin);for(;!isalpha(st[n]);--n);
	exkmp();
	for(int i=1,j,k,u;i<=n;)
	{
		j=i,k=i+1,u=1;if(!ans[i])ans[i]=i;
		for(;k<=n&&st[k]>=st[j];k++)
		{
			if(st[k]==st[j])
			{
				int t=(k-i)%u+i;
				if(!ans[k])
				{
					if(ans[t]<i)ans[k]=i;
					else ans[k]=chkmin(i,k-(t-ans[t]),k);
				}
				j++;
			}
			else
			{
				u=k-i+1;j=i;if(!ans[k])ans[k]=i;
			} 
		}
		i+=(k-i)/u*u;//cout<<i<<endl;
	}
	for(int i=1;i<=n;++i)out(ans[i]),*oh++=' ';*oh++='\n';
	fwrite(obuf,1,oh-obuf,stdout);
}