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

jiezecheng · 2026-04-25 17:02:52 · 题解

令 Bajtazar 想要的文字为 s，下标从 1 开始。一个字符串的反转定义为题目中的反向字符串，表示为 \overline{s}。

如果我们要枚举合法的模版，这个模版一定要包含 s_1，且买一个模版会送它的反转。 这意味这我们一定会买 s 的某一前缀（否则无法匹配前缀）。

暴力

假设我们现在枚举了一个 l，表示购买 s_{[1:l]} 的模版。

将问题抽象为一个铺路问题。

• 初始时所有字符都是没有铺过的。
• 有两种瓷砖 s_{[1:l]} 与 \overline{s_{[1:l]}}。
• 我们每次都从路面最左端开始。设已经铺过的路为 s_{[1:p]}，合法的起点为 [1,p+1]，接下来要选一种瓷砖，在某个合法起点上铺下，使新覆盖的区域尽量向右延伸，并更新 p。
• 为了将 s 铺完，我们每次都选最靠右的能铺上瓷砖的下标。

以样例 1 为例：

此时枚举 l=5，则模版 t=\texttt{abcab},\overline{t}=\texttt{bacba}。

此时 p=0。

• 在 [1,1] 选择下标 1，因为 s_{[1 :l]}=t，此时将 p 铺到了 5。

• 在 [1,6] 选择下标 4，因为 s_{[4 :4+l-1]}=s_{[4,8]}=t，此时将 p 铺到了 8。

• 在 [1,9] 选择下标 8，因为 s_{[8 :8+l-1]}=s_{[8,12]}=\overline{t}，此时将 p 铺到了 12。

• 在 [1,13] 选择下标 12，因为 s_{[12 :12+l-1]}=s_{[12,16]}=t，此时将 p 铺到了 16。

由于最后 p=n，可得 l=5 满足要求。

那么如果我们如此暴力匹配，时间复杂度是多少呢？

当 s=\texttt{abcabcabcabc},l=6，即 t=\texttt{abcabc}。 有如下可行的匹配。

如果你要更新红蓝黄三种匹配，倒不如只更新红黄两种颜色，也就是说，查询 [1,p+1] 中可以匹配 t 或 \overline{t} 的最右下标。

可以发现，两次更新一定会至少更新 \frac{l}{2}。则对于一个 l，时间复杂度为 O(n \log n)（调和级数），总时间复杂度为 O(n^2\log n)。

顺便说一下，如果没有 [1,p+1] 中可以匹配 t 或 \overline{t} 的最右下标，或在扩展后的 p 还没大于原来的 p，则这个 l 不满足要求。

优化

如何优化？

瓶颈有二。

1. 子串与前缀的匹配。

我们可以用 Z 函数来直接查询任意下标 i 开始是否可以匹配长度为 l 的前缀。即如果 z_i\ge l，那么 s_{[i,i+l-1]}=t。

同理，也可以用 Z 函数查询任意下标 i 开始是否可以匹配 \overline{s_{[1:l]}}，即将 \overline{s} 与 s 匹配出一个 z 数组，将其反转，记为 \overline{z}，如果 \overline{z}_{i+l-1}\ge l，那么 t=s_{[1:l]}。

2. 如何查询 [1,p+1] 中可以匹配 t 或 \overline{t} 的最右下标。

我们考虑到，到底一个点为什么不能作为匹配起点。

• 初始时所有位置都可用（都可以作为起点）。

• 随着 l 增大，某些位置的 z 值不够用了（l > z_i），这些点，无法成为起点了，且由于我们的 l 时从大到小枚举的，这些点就再也用不着了！

• 查询时我们可以从 p+1 一路向左，找到第一个仍有效的起点。

所以我们可以利用并查集来维护这个信息。如果一个点 i 无效了，那么可以让 i 在并查集中的父亲指向 i-1 的父亲，每次可以直接使用 \text{find(}p+1)，这样就可以做到 O(\alpha(n)) 查询了！

总时间复杂度 O(n\log n \alpha (n))，完全可以通过此题。

代码

还有一些小细节，如最开始 \text{fa}_{n+1}\sim\text{fa}_{2n}=n 等，加油吧。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int z[N];
void get_z(string s,int n){
    for(int i=2;i<=n;i++) z[i]=0;
    z[1]=n;
    int l=1,r=1;
    for(int i=2;i<=n;i++){
        if(i<=r) z[i]=min(z[i-l+1],r-i+1);
        while(i+z[i]<=n and s[z[i]+1]==s[i+z[i]]) z[i]++;
        if(i+z[i]-1>r){
            l=i;
            r=i+z[i]-1;
        }
    }
}
int z_fr[N];
int z_re[N];

struct DSU{
    int fa[N];
    int n;
    DSU(int sze){
        n=sze;
        for(int i=0;i<=n;i++) fa[i]=i;
        for(int i=n+1;i<=n+n;i++) fa[i]=n;
    }
    int Find(int x){
        if(fa[x]==x) return x;
        fa[x]=Find(fa[x]);
        return fa[x];
    }
    void del(int x){
        fa[x]=Find(x-1);
    }
    void print(){
        for(int i=1;i<=n;i++) cout<<Find(i)<<" ";
        cout<<"\n";
    }
};
vector<int> dele_fr[N];
vector<int> dele_re[N];

int main(){
    string s;
    cin>>s;
    int n=s.size();
    string rs=s;reverse(rs.begin(),rs.end());
    get_z(" "+s,n);
    for(int i=1;i<=n;i++) z_fr[i]=z[i];
    get_z(" "+s+"#"+rs,n+n+1);
    for(int i=n+2;i<=n+n+1;i++) z_re[i-n-1]=z[i];
    reverse(z_re+1,z_re+n+1);
//  for(int i=1;i<=n;i++) cout<<z_fr[i]<<" ";
//  cout<<"\n";
//  for(int i=1;i<=n;i++) cout<<z_re[i]<<" ";
//  cout<<"\n";
    DSU d_fr(n),d_re(n);
    for(int i=1;i<=n;i++) dele_fr[z_fr[i]+1].push_back(i);
    for(int i=1;i<=n;i++) dele_re[z_re[i]+1].push_back(i);

    for(int len=1;len<=n;len++){
        for(int i:dele_fr[len]) d_fr.del(i);
        for(int i:dele_re[len]) d_re.del(i);
        int now=0;
//      d_fr.print();
//      d_re.print();

//      cout<<"len : "<<len<<"\n";
        while(1){
//          cout<<now<<"\n";
            int fa_fr=d_fr.Find(now+1);
            int fa_re=d_re.Find(now+len);
            if(fa_fr+len-1<=now and fa_re<=now) break;
            now=max(fa_fr+len-1,fa_re);
            if(now>=n){
                cout<<len<<" ";
                break;
            }
        }
    }
}