[SDOI2017] 文本校正

henryhu2006 · 2023-11-09 17:11:16 · 题解

本文的所有情况的时间复杂度均为 \mathcal O(n)，不需要后缀数据结构。

题意

多测，每次给定两个（正整数）串 s 和 t，判断是否可以将 t 划分成三个非空段，任意排列后拼接在一起，得到串 s，并构造方案。

## 分析显然需要对拼接顺序分类讨论，将 $t$ 的三个划分段标记为 $1,2,3$，用一个排列来描述如何拼接出 $s$。一共有 $123,132,213,231,312,321$ 六种情况，但是可以发现，有些排列是本质相同的，一共有四种情况： - $123$ 显然直接判断 $s=t$ 即可。 - $231,312$ 本质相同，相当于判断 $s,t$ 是否循环同构。 - $132,213$ 本质相同，相当于保留一个公共前缀或者后缀，要求剩下的前缀或后缀循环同构。 - $321$ 可以考虑将其反转和原串对齐。 ## $231,312

这一部分较为容易，可以将 t 倍长后用哈希或者 KMP 判断 s 是否在其中出现即可。需要注意三段都非空。

const ull B=1e8+7; ull h[N*2];
bool solve2(){
    ull H=0,P=1;
    for(int i=1;i<=n;++i)
        t[n+i]=t[i],H=B*H+s[i],P*=B;
    for(int i=1;i<=2*n;++i) h[i]=B*h[i-1]+t[i];
    for(int l=2;l<=n;++l)
        if(H==h[l+n-1]-h[l-1]*P){
            if(l>2) return print(l,n,1,1,2,l-1);
            else return print(l,n-1,n,n,1,l-1);
        }
    return 0;
}

132,213

我们考虑 213，对于 132，是完全对称的。

首先可以求出 s,t 之间的 Z 函数，设 s 的后缀和 t 的 LCP 为 zs，t 的后缀和 s 的 LCP 为 zt。

设 1 的长度为 i，2 的长度为 j，s,t 的最长公共后缀长度为 p，那么有解等价于：

zs_{j+1}\ge i
zt_{i+1}\ge j
i+j\ge n-p

如果打算 \mathcal O(n\log n) 做，用树状数组扫一遍即可。

枚举 i+j，那么 1 是 s[1,i+j] 的后缀，是 t 的前缀。因此使用 KMP，用 t 来匹配 s，那么所有可能的 1 串在 Fail 树的根链上。

因此为了第三个条件尽可能满足，我们可以在对 t 串预处理 KMP 的时候算出 Fail 树根链上 i+zt_{i+1} 的最大值。在用 t 匹配 s 时，KMP 算到的失配指针 j 就是根链的底部。

于是时间复杂度是 \mathcal O(n) 的。

int z1[N],z[N],nxt[N],mx[N];
void exkmp(int *z,int *Z,int *t,int *s){
    memset(z+1,0,4*n);
    for(int i=1+(z==Z),l=0,r=0;i<=n;++i){
        if(r>=i) z[i]=min(r-i+1,Z[i-l+1]);
        while(i+z[i]<=n&&t[z[i]+1]==s[i+z[i]]) ++z[i];
        if(i+z[i]-1>r) l=i,r=i+z[i]-1;
    }
} 
bool solve3(bool rev){
    memset(nxt+1,0,4*n);
    exkmp(z1,z1,s,s),exkmp(z,z1,s,t);

    int p=0; while(s[n-p]==t[n-p]) ++p;
    if(!p) return 0;
    iota(mx+1,mx+n,1);
    for(int i=2,j=0;i<=n;++i){
        while(j&&t[i]!=t[j+1]) j=nxt[j];
        if(t[i]==t[j+1]) ++j; nxt[i]=j;
        if(j) mx[i]=(mx[j]+z[mx[j]+1]>i+z[i+1]?mx[j]:i);
    }

    for(int i=1,j=0;i<n;++i){
        while(j&&s[i]!=t[j+1]) j=nxt[j];
        if(t[j+1]==s[i]) ++j;
        if(mx[j]+z[mx[j]+1]>=i&&i>=n-p){
            int r=mx[j];
            if(!rev) return print(r+1,i,1,r,i+1,n);
            else return print(1,n-i,n-r+1,n,n-i+1,n-r);
        }
    }
    return 0;
}

321

将 s 反转，问题变为是否可以将 t 划分成三段使得将每段反转后和 s 一样。

然后就是各种各样的巨型后缀数据结构，但有一个非常 Ad-Hoc 的构造：将 s,t 的字符相隔排列：t_1s_1t_2s_2\cdots t_ns_n，则一个区间可以作为分割段，当且仅当其在构造串中所对应的子串（显然长度为偶数）是一个回文串。

这个构造的充分和必要性都是容易证明的。于是问题就变成了判断一个字符串是否能划分成三个偶回文串。

显然需要 Manacher，但是后面的问题看似简单，但是要做到线性非常困难，保底可以用 NTT 做到 \mathcal O(n\log n)。

枚举第一个回文串，则要将后缀划分成两个回文串。此时有一个非常难发现也难证明的性质。

考虑一个字符串，如果有三种方案对其进行划分（不一定成立），分别为 [1,a],[a+1,n]; [1,b],[b+1,n];[1,c],[c+1,n]，设 a<b<c，若 [1,a] 不是回文串，[a+1,n] 是回文串；[1,b] 和 [b+1,n] 都是回文串；[1,c] 是回文串，[c+1,n] 不是回文串。

如果 b\le 0.5n，则右边的区间长度大于 0.5n，而 a<b，所以 [a+1,n] 的区间长度大于 [b+1,n]，必然长度小于 [b+1,n] 的两倍。对于 b\ge 0.5n，是对称的，可以得到另外一边的回文串小于左侧的两倍。有众所周知的回文串性质：一个回文串长度大于一半的回文前后缀，此回文串存在 Period。

不妨考虑 b\le 0.5n，那么 [0,c] 都被划分成若干个 Period（我们考虑最小的 Period），且 Period 长度为 \gcd(b,c) 的约数。如果 a 不是 Period 的倍数，则 [a+1,n] 有残缺不全的 Period 前后缀，从 a+1 到 c。则 n 左侧长度为 c-a 的段也是可知且残缺的。在 [b+1,n] 中也进行对称，则 b+1 后面一小段也是残缺的。

以此类推，辗转相除，到 n 距离为 \gcd(n-a,n-b) 倍数的地方都有残缺的 Period。或者说有一个大小为 \gcd(n-a,n-b) 的 Period。两者有公共区域，所以必然要求 \gcd(n-a,n-b) 是 \gcd(b,c) 的倍数。可以得出，n 是 \gcd(b,c) 的倍数。

可以得出 n-a,a 也是 \gcd(b,c) 的倍数，和 a 不是 Period 的倍数矛盾。

于是可以得到 \gcd (b,c) 是整个串的 Period。

回到原问题，我们只需要考虑 i 之后最小的 j 使得 [j,n] 为回文串，以及最大的 k，使得 [i+1,k] 为回文串，试图将其更新答案，显然一个必要条件是 j<k（对应上文 a<c）。如果更新成功，那么就不管了；如果更新失败，那么就会出现和上面结论描述一样的情况，得出 \gcd(b,c) 是整个后缀的 Period，显然这种情况可以被上述的方法判掉，和假设矛盾。

所以只需要考虑这两种情况，算出所有回文后缀，直接用指针扫，可以解决 j。对于 k 最大，等价于回文中心的位置最大，这是 Manacher 好处理的，具体实现见代码。

时间复杂度 \mathcal O(n)。

代码中，s 已经完成反转。

int c[N*2],w[N*2],ra[N*2],st[N],top;
void cmax(int &x,int y){if(x<y) x=y;}
bool palin(int l,int r){return w[l+r>>1]>=(r-l+1)/2;}
bool solve4(){
    memset(ra+1,0,8*n);
    memset(w+1,0,8*n);
    for(int i=1;i<=n;++i) c[2*i-1]=t[i],c[2*i]=s[i];

    for(int i=1,mx=0,id;i<n*2;++i){
        if(i<mx) w[i]=min(mx-i,w[id*2-i]);
        while(i+w[i]+1<=n*2&&i-w[i]&&c[i-w[i]]==c[i+w[i]+1]) ++w[i];
        if(i+w[i]>=mx) mx=i+w[i],id=i;
        cmax(ra[i-w[i]+1+((i+w[i])&1)],i);
    }

    top=0;
    for(int i=1;i<=n*2;i+=2)
        if(palin(i,n*2)) st[++top]=i;
    for(int i=3;i<=n*2;++i) cmax(ra[i],ra[i-2]);
    for(int i=2,j=1;i<n*2;i+=2)
        if(palin(1,i)){
            while(j<=top&&st[j]<=i) ++j;
            if(j<=top){
                if(palin(i+1,st[j]-1))
                    return print((st[j]+1)/2,n,(i+2)/2,st[j]/2,1,i/2);
                if(ra[i+1]>=i+1&&palin(ra[i+1]*2-i+1,n*2))
                    return print(((ra[i+1]*2-i+1)+1)/2,n,(i+2)/2,(ra[i+1]*2-i+1)/2,1,i/2);
            }
        }
    return 0;
}

完整代码见提交记录 #1931412。