自动搬运

查看原文

来自洛谷，原作者为

	Math_rad_round 旋转卡壳有2^4种读法，你知道吗？||NOIP退役苕皮

搬运于2025-08-24 21:34:24，当前版本为作者最后更新于2022-02-09 09:04:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

为讨论方便，我们令下文中 $|a|\geq|b|$

对 a、b，如果它们各自删除不超过其自身长度一半的字符能够相等 也就意味着 a 剩下的字符串和 b 剩下的字符串是相等的，即:

距离为 $1$ 等价于 最长公共子序列长度 $\geq\frac{|a|}{2}$

同时也可以推断出，如果我们在 b 中随便插入 $|b|$ 个字符，得到的字符串仍然和 b 距离为 $1$

那么我们可以不断地往 b 上插入 $|b|$ 个字符，也就使最长公共子序列长度增加了 $|b|$，同时 $|b|$ 也翻了一倍

直到最长公共子序列长度达到 $\frac{|a|}{2}$ ，这时只需要再有一次操作即可完成

时空复杂度均为 $O(|a||b|)$，也就使求最长公共子序列。

注意：两字符串相等时答案为 $1$

代码：

#include<iostream>
using namespace std;
string a,b;
int f[300][300];
int main(){
	cin>>a>>b;
	int n=a.length(),m=b.length();
	if(n<m){
		swap(n,m);swap(a,b);
	}
	if(a==b){//特判相等 
		cout<<"1";return 0;
	}
	int ans=0;
	for(int i=1;i<=n;i++){//求最长公共子序列
		for(int j=1;j<=m;j++){
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			if(a[i-1]==b[j-1])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
			ans=max(f[i][j],ans);
		}
	}
	int cnt=0;
	while(ans*2<n){
		cnt++;ans+=m;m+=m;
	}cnt++;
	cout<<cnt;
	return 0;
}