编辑距离和最长公共子序列（动态规划经典题）

不念不忘少年蓝@ 2022-06-10 04:38 92阅读 0赞

编辑距离：

描述：  
设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括:  
(1)删除一个字符;  
(2)插入一个字符；  
(3)将一个字符改为另一个字符。  
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离,记为d(A,B)。试设计一个有效[算法][Link 1],对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。

要求：  
输入：第1行是字符串A,第2行是字符串B。  
输出：字符串A和B的编辑距离d(A,B)

1. 设状态：f\[i\]\[j\]表示s1串的前i个字符和s2串的前j和字符相等时s1串最少字符操作次数；

2. 初始状态：f\[i\]\[0\]=i;//当s2串没有字符时，最少操作次数为将s1串的所有字符删除；

f\[0\]\[i\]=i;//当s1串没有字符时，最少操作次数为在s1串插入s2串对应位置一样的字符；

最终状态：f\[m\]\[n\];

3. 状态转移方程：**当s1\[i-1\]==s2\[j-1\] f\[i\]\[j\]=f\[i-1\]\[j-1\];**

**当s1\[i-1\]!=s2\[j-1\] f\[i\]\[j\]=min(f\[i-1\]\[j-1\],f\[i\]\[j-1\],f\[i-1\]\[j\])+1;**

说明：

**f\[i-1\]\[j-1\]+1:将s1\[i\]改为s2\[j\];**

**f\[i\]\[j-1\]+1:s1\[i\]后插入s2\[j-1\];**

**f\[i-1\]\[j\]+1:删除s\[i\].**

/*
    sfdqxbw
    gfdgw
    */ 
    #include<iostream>
    #include<cstring>
    using namespace std;
    int f[202][201];//f[i][j]表示A串的前i个字符和B串的前j个字符相等时的最少操作次数
    char s1[202],s2[202];//s1为A串，s2为B串
    int i,j,k,m,n;
    int main()
    {
    	cin>>s1>>s2;
    	m=strlen(s1);
    	n=strlen(s2);
    	for(int i=1;i<=m;i++) f[i][0]=i;//初始化，将A串的内容全部删除 
    	for(int i=1;i<=n;i++) f[0][j]=i;//初始化，将A串插入和B串i位置相同的字符
    	for(int i=1;i<=m;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1];
    			else f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
    		}
    	}
    	cout<<f[m][n]<<endl;
    	return 0;
    }

最长公共子序列：

1. 设状态：f\[i\]\[j\];//s1串的前i个字符和s2串的前j个字符的最长公共子序列长度；

2. 初始状态： f\[0\]\[0\]=0;

最终状态：f\[m\]\[n\];

3. 状态转移方程：

**当s1\[i-1\]==s2\[j-1\] f\[i\]\[j\]=f\[i-1\]\[j-1\]+1;**

**当s1\[i-1\]!=s2\[j-1\] f\[i\]\[j\]=max(f\[i\]\[j-1\],f\[i-1\]\[j\]);**

说明：

**f\[i\]\[j\]=f\[i\]\[j-1\]:s2\[j\]不在公共子序列中**

**f\[i\]\[j\]=f\[i-1\]\[j\]:s1\[i\]不在公共子序列中**

/*
    ABCBDAB
    BDCABA
    */ 
    #include<iostream>
    #include<cstring>
    using namespace std;
    int f[202][202];//A串的前i个字符和B串的前j个字符的最长公共序列长度
    char s1[202],s2[202]; 
    int main()
    {
    	cin>>s1>>s2;
    	int m=strlen(s1);
    	int n=strlen(s2);
    	for(int i=1;i<=m;i++)
    	{
    		for(int j=1;j<=n;j++)
    		{
    			if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1;
    			else f[i][j]=max(f[i-1][j],f[i][j-1]);
    		}
    	}
    	cout<<f[m][n];
    	return 0;
    }

[Link 1]: http://lib.csdn.net/base/datastructure

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关 [动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串 LintCode：[https://www.lintcode.com/problem/longest-common-substring/descri...

约定不等于承诺〃/ 2024年04月18日 17:10/ 0 赞/ 75 阅读

相关动态规划：最长公共子序列

动态规划：最长公共子序列前言一、动态规划 -------------------- 前言给定两个字符串 text1 和 text2，返回这两个

妖狐艹你老母/ 2024年03月16日 18:40/ 0 赞/ 113 阅读

相关【必备算法】动态规划：LeetCode题（五）1143. 最长公共子序列，72. 编辑距离

[1143. 最长公共子序列²][1143.] 给定两个字符串 `text1` 和 `text2`，返回这两个字符串的最长公共子序列的长度。一个字符串的子序列是指

我不是女神ヾ/ 2022年11月06日 02:56/ 0 赞/ 6 阅读

相关编辑距离，最长公共子序列，最长公共子串，最长递增子序列

1.编辑距离编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将

忘是亡心i/ 2022年08月28日 14:44/ 0 赞/ 253 阅读

相关最长公共子序列（动态规划）

【题⺫】给定两个字符串 str1 和 str2，返回两个字符串的最长公共子序列。【举例】 str1 =“1 A2 C 3 D 4 B5 6 ”， str2

本是古典何须时尚/ 2022年08月18日 02:19/ 0 赞/ 232 阅读

相关动态规划：求最长公共子串/最长公共子序列

最长公共子序列和最长公共子串区别最长公共子串（Longest Common Substring）与最长公共子序列（Longest Common Subsequence

我不是女神ヾ/ 2022年08月08日 03:24/ 0 赞/ 280 阅读

相关编辑距离和最长公共子序列（动态规划经典题）

编辑距离：描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括: (1)删除一个字符; (2)插入一个字符； (

不念不忘少年蓝@/ 2022年06月10日 04:38/ 0 赞/ 93 阅读

相关最长公共子序列（动态规划）

【例9.9】最长公共子序列时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个给定序列的子序列是在该序列中删去若干元素后得到

╰半橙微兮°/ 2022年06月08日 10:06/ 0 赞/ 265 阅读

相关动态规划-最长公共子序列

一，问题描述给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这

痛定思痛。/ 2022年05月11日 11:50/ 0 赞/ 304 阅读

相关【动态规划】最长公共子序列与最长公共子串

[来源][Link 1] 1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串 cnblogs belong 比如序列

「爱情、让人受尽委屈。」/ 2021年06月24日 16:12/ 0 赞/ 545 阅读