自动搬运

查看原文

来自洛谷，原作者为

	henryhu2006 **

搬运于2025-08-24 21:52:39，当前版本为作者最后更新于2023-11-09 17:11:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

题意

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

$\sum |s|,\sum |t|\le 10^6$。

分析

显然需要对拼接顺序分类讨论，将 $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。

$321$ 的第二个结论受 提交记录 #799188 启发。