首页 > 其他分享 >编辑字符串距离

编辑字符串距离

时间:2023-05-31 16:34:33浏览次数:40  
标签:字符 sitting int 距离 char 编辑 字符串 include


题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1183


题意:编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另

     一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删

     除一个字符。





     例如将kitten转化成sitting:



sitten (k->s)
 

 

 
       sittin (e->i)
 
       sitting (->g)





     所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这



     个概念。 给出两个字符串a,b,求a和b的编辑距离。





代码:



#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
const int N = 1005;

int dp[N][N];
char S[N],T[N];

int Lenv(char S[],char T[])
{
    int n = strlen(S);
    int m = strlen(T);
    for(int i=0; i<=n; i++)
        dp[i][0] = i;
    for(int i=0; i<=m; i++)
        dp[0][i] = i;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
            if(S[i-1] == T[j-1])
                dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
            else
                dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);
        }
    }
    return dp[n][m];
}

int main()
{
    while(scanf("%s%s",S,T)!=EOF)
        printf("%d\n",Lenv(S,T));
    return 0;
}




标签:字符,sitting,int,距离,char,编辑,字符串,include
From: https://blog.51cto.com/u_16146153/6388093

相关文章

  • UE4字符串调试日志
    #在运行时打印输出信息原作者:Rama(opensnewwindow)此文为Logs,PrintingMessagesToYourselfDuringRuntime(opensnewwindow)的原创翻译,本文内容版权归原文所有,仅供学习,如需转载望注本文地址,翻译不易,谢谢理解。#概述Logs很重要,因为它通过给你反馈来让你知道:你的......
  • 神经网络中embedding层作用——本质就是word2vec,数据降维,同时可以很方便计算同义词(各
    Embeddingtflearn.layers.embedding_ops.embedding(incoming,input_dim,output_dim,validate_indices=False,weights_init='truncated_normal',trainable=True,restore=True,reuse=False,scope=None,name='Embedding')Embeddinglayerforase......
  • 最小距离和
    题目:在一个平面坐标系中给定()个点,坐标为范围的绝对值均在范围内,在轴上找一点    使得这点到所有点的距离之和最短。 分析:本题方法是三分,我们知道三分满足的条件是这个对象必须是单峰函数。题目要求找到最小值,那么也就是说   这个距离之和是一个下凸函数,现在来开始证明。......
  • 椭圆中心到椭圆切线的距离
    本文将要讨论的是椭圆中心到椭圆切线的距离公式,在求这个距离之前,我们首先要知道两个定理。定理1:椭圆          上的点到椭圆左,右焦点的距离分别是和,其中是椭圆的离心率。定理2:椭圆(1)上的点处的切线方程是     实际上这两个定理都是很容易证明的,这是高中所学的知识......
  • 关于C++字符串的一些函数
    其实印象里,c的char用法反倒比c++的string深一点,可能是因为我对string的运用太少了吧。 提到C++的string,就得先提一下首先提一下C的char类型,毕竟C++是根据C延展过来的,继承了C的特性,而且C本身是没有string这个东西的。 char是什么?一个关键字,用于声明一个变量是字符类型。好吧,......
  • 字符串解压缩问题——贪心算法
     importsysdefload_data():returnsys.stdin.read()defget_position_map(s):result={}stack=[]fori,cinenumerate(s):ifc=="[":result[i]=-1stack.append(i)elifc=="......
  • VST实例(8)编辑
    VST的单元格支持编辑,使用普通的编辑很简单,VST提供了一个编辑器,是一个继承自TCUSTOMEDIT的编辑器。TStringEditLink=class(TInterfacedObject,IVTEditLink);1、发出编辑请求向VST发出编辑请求,有以下三种方式:第一种方式是,VST可以在treeoptions里设置toEditable,可在鼠标放到......
  • vst实例(9)创建编辑器
    先上编辑器单元的代码:uniteditlink;interfaceusesWindows,Messages,SysUtils,Classes,Graphics,Controls,Forms,Dialogs,StdCtrls,VirtualTrees;typetcomboeditlink=class(TInterfacedObject,IVTEditLink)privateFedit:TComboBox;itemstrs:......
  • 拼接字符串
      在Python中,join()是字符串的一个方法,用于将一个可迭代对象中的元素连接成一个字符串 ......
  • MySQL数据库,字符串字段拆分
    MySQL数据库,字符串字段拆分英文姓名存储在一个字段如何拆分出firstname和lastname查询语句SELECTREPLACE(name,CONCAT('',SUBSTRING_INDEX(name,'',-1)),'')ASfirstname,SUBSTRING_INDEX(name,'',-1)ASlastnameFROMpeople;SUBSTRING_INDE......