qwaszx · 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); }
