自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:22:48，当前版本为作者最后更新于2020-03-17 14:19:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题面传送门。

题意简述：给定两个字符串 $s,t$。每次可以切除 $t$ 的一个前/后缀并保证其为切割后的 $t$ 的子串。求得到 $s$ 的最少操作数或给出无解。

题目可以理解为：每次操作将 $s$ 的一个子串拼在其前/后。求得到 $t$ 的最少操作数。

---

一些约定：

设 $m=|s|,n=|t|$。设区间 $[l,r]$ 为 $t$ 的第 $l$ 位至第 $r$ 位字符组成的字符串。

• 如何判断无解：如果 $s$ 没有在 $t$ 中出现，或者 $t$ 出现了 $s$ 没有的字母，即无解。可以 $O(n^2)$ 暴力判断，也可以 $O(n)$ KMP 求解。std 使用 $O(n^2)$ 暴力判断。

---

Subtask $1$：$s=t$。

输出 $0$ 即可。

Subtask $2$：$s$ 仅包含小写字母 $\texttt{a}$。

先判断是否无解，否则答案为最小的满足 $m\times 2^c\geq n$ 成立的整数 $c$。

Subtask $3$：$n\leq 100$。

区间 DP。设 $f_{i,j}$ 为 $s$ 扩展到区间 $[l,r]$ 的最少步数。转移时枚举粘贴字符串的长度，暴力匹配。枚举 $l,r:O(n^2)$，转移枚举长度 $:O(n)$，暴力匹配 $:O(n)$。时间复杂度 $O(n^4)$，常数极小。

Subtask $4$：$n\leq 500$。

将暴力匹配改成字符串哈希即可做到 $O(1)$ 匹配。总时间复杂度 $O(n^3)$，常数较小。

如果实现精细 + 极小常数，$O(n^4)$ 也许可以暴力艹过去。

Subtask $5$：$n\leq 1.5\times 10^3$。

验题人

法时间复杂度为 $n^2\log n$。这里放上他的原话（有删减）：

“如果已经算出了 $f_{l,r}$，考虑它能影响哪些更大的区间的 $f$ 值。显然只能从两端扩展。”

“以往左为例，能扩展到 $l'$（能影响 $f_{l',r}$）当且仅当 $[l',l-1]$ 是 $[l,r]$ 的子串。那么所有 $l'$ 显然构成区间。”

“用 $z$ 算法算出 $t$ 中两两点的 LCS，区间 RMQ 即可得到最小的 $l'$，然后线段树区间更新维护。”

“还有一个小小的优化方法可以把它弄成 BIT。”

这里给出他的代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
int lowbit(int x){return x&-x;}
const int N=1500,M=1500;
int n,m;
char a[N+5],b[M+5];
int cov[N+1][M+1];
int lcP[N+1][M+1],Lcs[M+1][M+1];
int s;
char c[N+M+6];
void con(char s1[],int p1,int l1,char s2[],int p2,int l2){
	s=0;
	for(int i=p1;i<=l1;i++)c[++s]=s1[i];
	c[++s]='!';
	for(int i=p2;i<=l2;i++)c[++s]=s2[i];
}
int z[N+M+2];
void z_init(){
	z[1]=s;
	int zl=0,zr=0;
	for(int i=2;i<=s;i++)
		if(zr<i){
			z[i]=0;
			while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
			if(z[i])zl=i,zr=i+z[i]-1;
		}
		else if(i+z[i-zl+1]<=zr)z[i]=z[i-zl+1];
		else{
			z[i]=zr-i+1;
			while(i+z[i]<=s&&c[i+z[i]]==c[1+z[i]])z[i]++;
			zl=i;zr=i+z[i]-1;
		}
}
struct bitree{
	int val[M+2],mn[M+1];
	void init(){memset(val,0x3f,sizeof(val));memset(mn,0x3f,sizeof(mn));}
	void chkmn(int x,int v){
		if(v>=val[x])return;
		val[x]=v;
		while(x<=m)mn[x]=min(mn[x],v),x+=lowbit(x);
	}
	int Mn(int x){
		int res=inf;
		while(x)res=min(res,mn[x]),x-=lowbit(x);
		return res;
	}
}bit[M+1],bitr[M+1];
int lft[M+1][M+1],rit[M+1][M+1];
int dp[M+1][M+1];
int main(){
	cin>>b+1>>a+1;
	n=strlen(a+1);m=strlen(b+1);
	con(a,1,n,b,1,m);z_init();
	for(int i=1;i<=m;i++)if(z[n+1+i]==n)cov[i][i+n-1]=true;
	for(int i=1;i<=m;i++){
		con(b,i,m,b,1,m);z_init();
		for(int j=1;j<=m;j++)lcP[i][j]=z[m-i+1+1+j];
	}
	reverse(b+1,b+m+1);
	for(int i=1;i<=m;i++){
		con(b,i,m,b,1,m);z_init();
		for(int j=1;j<=m;j++)Lcs[m-i+1][m-j+1]=z[m-i+1+1+j];
	}
	for(int i=1;i<=m;i++)bit[i].init(),bitr[i].init();
	for(int i=m;i;i--)for(int j=i;j<=m;j++){
		dp[i][j]=cov[i][j]?0:min(bit[j].Mn(i),bitr[i].Mn(m-j+1));
		bit[j].chkmn(i-(lft[i][j]=max(lft[i][j-1],min(Lcs[j][i-1],j-i+1))),dp[i][j]+1);
		bitr[i].chkmn(m-(j+(rit[i][j]=max(rit[i+1][j],min(lcP[i][j+1],j-i+1))))+1,dp[i][j]+1);
	}
	cout<<(dp[1][m]==inf?-1:dp[1][m]);
	return 0;
}

Subtask $6$：$|s|=4$，数据随机。

留给乱搞。

Subtask $7$：$n\leq 5\times 10^3$。

不妨换个思路，设 $f_{l,r}$ 为区间 $[l,r]$ 往左边（即头部）能粘贴的子串长度最大值，$g_{l,r}$ 为区间 $[l,r]$ 往右边（即尾部）能粘贴的子串长度最大值。

如果求出了 $f$ 和 $g$，我们可以通过一遍 BFS 求出答案。BFS 具体实现方法见代码，这里不再赘述。

• 如何预处理 $f,g$？

  回忆一下 $f,g$ 的定义：区间 $[l,r]$ 往左/右能粘贴的子串长度最大值。如果认真思考，就能发现 $f_{l,r}$ 一定不小于 $f_{l,r-1}(l<r)$，因为区间 $[l,r-1]$ 能往左粘贴的子串，区间 $[l,r]$ 也一定能做到，其长度就具有单调性。$g$ 同理。合理运用单调性和字符串哈希，就能在 $O(n^2)$ 的时间内计算 $f,g$。

预处理 $f,g$ 时间复杂度 $O(n^2)$，BFS 时间复杂度 $O(n^2)$。时间复杂度 $O(n^2)$。

• 应评论区补充一点：不难发现每次扩展的长度越大越好。感性理解一下，类似上面 $f_{l,r}$ 一样，区间 $[l,r]$ 能够扩展的长度一定不小于 $[l+1,r]$ 或 $[l,r-1]$。

• 另外也可以直接 DP 求答案，按照区间长度从小到大扩展即可。

#include<bits/stdc++.h>
using namespace std;

#define ull unsigned long long
#define int short
#define pii pair <int,int>
#define fi first
#define se second

const int N=5e3+5;
const int bs=131;

ull hs[N],pw[N];
ull cal(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}

string s,t;
int f[N][N],g[N][N],dp[N][N],n;
queue <pii> q;

signed main(){
	cin>>t>>s,n=t.size(); if(s==t)puts("0"),exit(0);
	
	pw[0]=1; for(int i=1;i<=n;i++)pw[i]=pw[i-1]*bs;
	for(int i=0;i<n;i++)hs[i+1]=hs[i]*bs+(t[i]-'a');
	
	for(int i=1;i<=n;i++){
		int tmp=1;
		for(int j=i;j<=n;j++){
			while(tmp<i&&j-tmp+1>=i&&cal(i-tmp,i-1)==cal(j-tmp+1,j))tmp++;
			f[i][j]=tmp-1;
		} tmp=1;
		for(int j=i;j;j--){
			while(i+tmp<=n&&j+tmp-1<=i&&cal(j,j+tmp-1)==cal(i+1,i+tmp))tmp++;
			g[j][i]=tmp-1;
		}
	}
	
	int pos=t.find(s); if(pos==-1)puts("-1"),exit(0);
	while(pos!=-1)q.push({pos+1,pos+s.size()}),pos=t.find(s,pos+1);
	while(!q.empty()){
		int l=q.front().fi,r=q.front().se,dl=f[l][r],dr=g[l][r],d=dp[l][r]; q.pop(); 
		if(dl!=0){l-=dl; if(!dp[l][r])dp[l][r]=d+1,q.push({l,r}); l+=dl;}
		if(dr!=0){r+=dr; if(!dp[l][r])dp[l][r]=d+1,q.push({l,r}); r-=dr;}
	}
	cout<<(dp[1][n]?dp[1][n]:-1)<<endl; 
	return 0;
}