最短编辑距离

最短编辑距离：Levenshtein Distance

1-LD模板

P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

设 \(A\) 和 \(B\) 是两个字符串。我们要用最少的字符操作次数，将字符串 \(A\) 转换为字符串 \(B\)。这里所说的字符操作共有三种：

1. 删除一个字符；
2. 插入一个字符；
3. 将一个字符改为另一个字符。

\(A, B\) 均只包含小写字母。

输入格式

第一行为字符串 \(A\)；第二行为字符串 \(B\)；字符串 \(A, B\) 的长度均小于 \(2000\)。

输出格式

只有一个正整数，为最少字符操作次数。

样例 #1

样例输入 #1

sfdqxbw
gfdgw

样例输出 #1

4

提示

对于 \(100 \%\) 的数据，\(1 \le |A|, |B| \le 2000\)。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2050;

int dp[MAX][MAX];
string s1,s2;
int l1,l2;

int main(void){
	cin>>s1>>s2;
	l1 = s1.length();
	l2 = s2.length();
	s1 = " " + s1;
	s2 = " " + s2;
    //初始化边界
	for(int i = 0 ; i <= l1 ; i ++){
		dp[i][0] = i;
	}
	for(int i = 0 ; i <= l2; i ++){
		dp[0][i] = i;
	}
	for(int i = 1 ; i <= l1 ; i ++){
		for(int j = 1 ; j <= l2 ; j ++){
			if(s1[i] == s2[j]){
				dp[i][j] = dp[i-1][j-1];//跳过
			}else{
				dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);//插入，删除
				dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);//修改
			}
		}
	}
	cout<<dp[l1][l2]<<endl;
	
	return 0;
}

2-LD+路径回溯

CAIP 2022 RC-u4 变牛的最快方法

这里问的是把任意一种动物的图像变成牛的方法…… 比如把一只鼠的图像变换成牛的图像。方法如下：

• 首先把屏幕上的像素点进行编号；
• 然后把两只动物的外轮廓像素点编号按顺时针记录下来；
• 用最少的变换次数将鼠的轮廓变成牛的 —— 这里仅允许对鼠的轮廓进行 3 钟操作：

1. 插入一个像素编号
2. 删除一个像素编号
3. 更改一个像素编号

输入格式

输入分别在两行中给出两种动物的轮廓像素点编号，编号为 (0,106] 区间内的整数，允许重复。轮廓以编号 −1 结尾，这个编号不算在轮廓内。题目保证每种动物的轮廓包含不超过 1000 个像素点。

输出格式

在第一行中输出从第一只动物变换成第二只动物需要的最少变换次数。

在第二行中顺次描述对第一只动物轮廓的每个像素所作的操作：

• 如果这个像素被删除，则在对应位置输出 0
• 如果这个像素被改变，则在对应位置输出 1
• 如果这个像素不变，则在对应位置输出 2
• 如果这个像素前面或者后面插入了一个像素，则在插入的位置输出 3

答案可能不唯一，输出任何一种可能的解都可以。行首尾和数字间均无空格。

输入样例

13 5 6 20 2 20 1 13 9 20 3 28 3 34 6 25 233 -1
3 5 6 20 6 20 3 5 9 3 9 20 3 6 6 25 233 -1

输出样例

8
122212112023121222

样例解释

1、13 更改为 3，随后 5、6、20 不变 2、2 更改为 6，下一个 20 不变 3、1 更改为 3 4、第二个 13 更改为 5，随后 9 不变 5、删除下一个 20，后面的 3 不变 6、在 28 的前面插入 9 7、28 更改为 20，后面的 3 不变 8、34 更改为 6，后面的 6、25、233 不变

代码

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1050;

int l1,l2;
int a1[MAX],a2[MAX];
pair<int,int> pre[MAX][MAX];
int op[MAX][MAX],dp[MAX][MAX];

//删除 0
//改变 1
//不变 2
//插入 3

int main(void){
	
	while(cin>>a1[++l1]){
		if(a1[l1] == -1) break;
	}l1--;
	while(cin>>a2[++l2]){
		if(a2[l2] == -1) break;
	}l2--;
	
	for(int i = 0 ; i <= l1 ; i ++){
		pre[i][0] = make_pair(i-1,0);
		dp[i][0] = i;
		op[i][0] = 0;
	}
	for(int i = 0 ; i <= l2 ; i ++){
		pre[0][i] = make_pair(0,i-1);
		dp[0][i] = i;
		op[0][i] = 3;
	}
	
	for(int i = 1 ; i <= l1 ; i ++){
		for(int j = 1 ; j <= l2 ; j ++){
			int add = dp[i][j-1] + 1; // 3
			int del = dp[i-1][j] + 1; // 0
			int rpl = dp[i-1][j-1] + (a1[i] != a2[j]); //1 ; 2
			int min_ = min(add,min(del,rpl));
			
			if(min_ == add){
				dp[i][j] = add;
				pre[i][j] = make_pair(i,j-1);
				op[i][j] = 3;
			}else if(min_ == del){
				dp[i][j] = del;
				pre[i][j] = make_pair(i-1,j);
				op[i][j] = 0;
			}else{
				dp[i][j] = rpl;
				pre[i][j] = make_pair(i-1,j-1);
				op[i][j] = a1[i] == a2[j] ? 2:1;
			}
		}
	}
	cout<<dp[l1][l2]<<endl;
	
	int x = l1;
	int y = l2;
	stack<int> ans;
	while(x > 0|| y > 0){
		ans.push(op[x][y]);
		pair<int,int> back = pre[x][y];
		x = back.first;
		y = back.second;
	}
	while(!ans.empty()){
		cout<<ans.top();
		ans.pop();
	}
	return 0;
}