题解：P12923 [POI 2021/2022 R3] 模板 2 / Szablon 2

zzy0618 · 2025-09-22 21:32:31 · 题解

想了一通没想到就是最暴力的做法。

对于每个长度 len，我们显然使用 S 的长度为 len 的前缀及其反串向后铺。假设我们已经铺路一段前缀，我们找到前缀最后一个可以向后拓展的位置 p，然后不断拓展即可。

这样做复杂度比想象中的要好的多。考虑每次向后拓展的长度。若连续两次拓展长度 <\frac{len}{2}，即像下图一样。

那不如直接用最后一条去拓展，并且是可行的。也就是说暴力拓展的次数是 O(n\log n) 的。

剩下的就是怎么找到最右边的拓展位置。正着和反着割跑一遍 exKMP，就可以找出每个位置开头的正串和反串与 S 的 lcp。

从小到大枚举 len，每次要删去一些正串与反串，总数量是 O(n) 的，并进行 O(n\log n) 次对于前缀的查询，使用线段树固然可以做到 O(n\log^2 n)，时间压力有点大。不如直接用并查集，删除 x 就将 fa_x 接到 fa_{x-1} 上即可，查询前缀 p 就是 \text{find}(p)。

由于不好按秩合并，复杂度没变，但常数要小很多。

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int N=1e6+5;
int n,z[N],rz[N];
vector<int> d[N],rd[N];
char s[N],t[N];
struct UU{
    int n,fa[N];
    void init(int N){n=N;
        for(int i=0;i<=n;++i)fa[i]=i;
    }int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }void del(int x){
        fa[x]=find(x-1);
    }int ask(int x){return find(min(x,n));}
}f,rf;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>s+1,n=strlen(s+1);
    for(int i=1;i<=n;++i)
        t[i]=s[n-i+1];
    z[1]=n;
    for(int i=2,l=0,r=0;i<=n;++i){
        if(i<=r)z[i]=min(z[i-l+1],r-i+1);
        while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])++z[i];
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }for(int i=1,l=0,r=0;i<=n;++i){
        if(i<=r)rz[i]=min(z[i-l+1],r-i+1);
        while(i+rz[i]<=n&&t[i+rz[i]]==s[rz[i]+1])++rz[i];
        if(i+rz[i]-1>r)l=i,r=i+rz[i]-1;
    }reverse(rz+1,rz+n+1);
    // for(int i=1;i<=n;++i)
    //     cout<<z[i]<<' ';
    // cout<<'\n';
    // for(int i=1;i<=n;++i)
    //     cout<<rz[i]<<' ';
    // cout<<'\n';
    f.init(n),rf.init(n);
    for(int i=1;i<=n;++i)
        d[z[i]+1].eb(i),rd[rz[i]+1].eb(i);
    for(int i=1;i<=n;++i){
        for(int v:d[i])f.del(v);
        for(int v:rd[i])rf.del(v);
        int p=0;
        while(1){
            int q=max(f.ask(p+1)+i-1,rf.ask(p+i));
            if(q<=p)break;
            if(q>=n){cout<<i<<' ';break;}
            p=q;
        }
    }cout<<'\n';
    return 0;
}