题解 P5334 【[JSOI2019] 节日庆典】

· · 题解

使用 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 且之前未被更新过，那么

考虑其正确性，我们在什么时候会进行新的一轮遍历？答案是末尾的 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);
}