首页 > 其他分享 >最短编辑距离

最短编辑距离

时间:2024-09-02 11:54:38浏览次数:13  
标签:AA 字符 包含 BB int 距离 最短 编辑 字符串

给定两个字符串 AA 和 BB,现在要将 AA 经过若干操作变为 BB,可进行的操作有:

  1. 删除–将字符串 AA 中的某个字符删除。
  2. 插入–在字符串 AA 的某个位置插入某个字符。
  3. 替换–将字符串 AA 中的某个字符替换为另一个字符。

现在请你求出,将 AA 变为 BB 至少需要进行多少次操作。

输入格式

第一行包含整数 nn,表示字符串 AA 的长度。

第二行包含一个长度为 nn 的字符串 AA。

第三行包含整数 mm,表示字符串 BB 的长度。

第四行包含一个长度为 mm 的字符串 BB。

字符串中均只包含大小写字母。

输出格式

输出一个整数,表示最少操作次数。

数据范围

1≤n,m≤10001≤n,m≤1000

输入样例:
10
AGTCTGACGC
11
AGTAAGTAGGC
输出样例:
4
#include <iostream>
using namespace std;
const int N=1010;
int n,m;
int f[N][N];
char a[N],b[N];
int main()
{
    scanf("%d%s",&n,a+1);
    scanf("%d%s",&m,b+1);
    for(int i=1;i<=m;i++)   f[0][i]=i;
    for(int i=1;i<=n;i++)   f[i][0]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=min(f[i][j-1]+1,f[i-1][j]+1);
            if(a[i]==b[j])  f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            
        }
    }
    cout<<f[n][m];
    
}

标签:AA,字符,包含,BB,int,距离,最短,编辑,字符串
From: https://blog.csdn.net/black_blank/article/details/141816331

相关文章

  • 求从一固定点到其余点的最短路算法及其matlab程序详解
    #################本文为学习《图论算法及其MATLAB实现》的学习笔记#################算法用途从一固定点到其他所有点的最短路的求法算法思想利用求任意两点间最短路的程序,即可求出从固定点到其他所有点的最短路,从而得到所有的最短路和最短距离。若想查看每条通路所包......
  • Affinity Photo 2.5.3.2516 x64 (照片编辑) 授权版
    AffinityPhoto是全球数百万创意和摄影专业人士的首选。这款备受赞誉的图像编辑软件拥有令人难以置信的速度、功能和精度,可以满足您编辑和修饰照片、创建多图层构图、精美的栅格绘图等一切需要。该版本已授权,可以免费使用。软件截图:使用说明:1、将压缩文件解压到某固定位......
  • 2024 年 13 个适用于 Linux 的最佳照片图像编辑器
      2024年13个适用于Linux的最佳照片图像编辑器   在本文中,我回顾了各种Linux发行版上可用的一些最佳照片编辑软件。这些不是唯一可用的照片编辑器,但却是Linux用户最流行和最常用的照片编辑器之一。1.GIMP首先,在列表中,我们有 GIMP,一个免费、开源、跨平台......
  • 581. 最短无序连续子数组
    581.最短无序连续子数组给你一个整数数组nums,你需要找出一个连续子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。请你找出符合题意的最短子数组,并输出它的长度。示例1:输入:nums=[2,6,4,8,10,9,15]输出:5解释:你只需要对[6,4,8,10,9]......
  • 已知弧度和半径,如何确定两点之间的距离?
    如果已知弧度(通常表示为θ)和半径(表示为r),可以使用以下几何关系来确定圆弧上的两点之间的实际线性距离。圆弧的长度(即两点之间的距离)可以通过以下公式计算:弧长=r×θ其中:θ 是以弧度为单位的角度(不是度数)。r 是圆的半径。结果是圆弧的长度,即两点沿着圆的路径的实际距离......
  • 一个.NET开源、现代、轻量级的文本编辑器
    前言今天大姚给大家分享一个.NET开源、免费(MITLicense)、现代、轻量级、具有极简主义设计的文本编辑器:Notepads。项目特点设计:采用Fluent设计语言,内置选项卡系统。性能:启动迅速,占用资源少。兼容性:支持从命令行或PowerShell启动。功能丰富:支持多行手写、Markdown实时预览、差异查看......
  • 对最长路(和最短路)的一些思考
    为了使得整篇文章显得更加人性化,咱们首先说一下最短路。声明:不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点不是讲解知识点,整篇文章建立在默认已经会的基础之上,然后提出一些个人见解。最短路此时的SPFA显得不再重要了(,咱们进入正题,说一下dijkstra。(堆优化的)迪杰......
  • Hausdorff Distance 和 Euclidean Distance Mean欧氏距离
    importtorchimporttorch.nnasnnclassHausdorffDistanceLoss(nn.Module):def__init__(self):super(HausdorffDistanceLoss,self).__init__()defforward(self,pred,target):#扩展为(B,N,1,D)和(B,1,M,D)pred=pred......
  • 【华为OD机试真题E卷】31、最大社交距离 | 机试真题+思路参考+代码分析(E卷复用)(C语言、
    文章目录一、题目......
  • vi文本编辑器
    Linux中最常用的文本编辑器vi:类UNIX操作系统的默认文本编辑器vim:vim是vi文本编辑器的增强版本三种工作模式之间的切换命令模式的基本操作跳转到文件的首行:1G或者gg跳转到文件的末尾行:G跳转到文件中的第#行:#G在编辑器中显示行号::setnu取消编辑器中的行号显示::setnonu向......