热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

序列和集合算法之序列比较

将一个序列变成另一个序列的最少修改步数。例如下图,将字符串A变成字符串B,所需要的步骤为6个步骤,match表示0步,其他操作表示1步:设计算法如下:publicsealedc

将一个序列变成另一个序列的最少修改步数。

例如下图,将字符串A变成字符串B,所需要的步骤为6个步骤,match表示0步,其他操作表示1步:

设计算法如下:

    public sealed class MinimumEditDistance
{
public int[,] CalculateDistance(string originalStr, String targetStr)
{
int LenA = originalStr.Length;
int LenB = targetStr.Length;
int[,] C = new int[LenA + 1, LenB + 1];
for (int i = 0; i <= LenA; C[i, 0] = i, i++) ;//targetStr为空串时的边界条件
for (int j = 0; j <= LenB; C[0, j] = j, j++) ;//originalStr为空串时的边界条件
for (int i = 1; i <= LenA; i++)
{
for (int j = 1; j <= LenB; j++)
{
//删除:考虑C[i-1,j],即i-1时已经达到最好情况,新添加的第i个字符需要删除掉
int candidateDel = C[i - 1, j] + 1;
//插入:考虑C[i,j-1],即已经在i的情况下能够达到j-1时的最好情况,此时如果考虑j的情况就是直接插入第j个字符
int candidateIns = C[i, j - 1] + 1;
//匹配:考虑C[i-1,j-1],即在i-1,j-1的情况下已经得到最好值,并且新近考虑的i和j字符相同,则无需任何额外动作
// int candidate = C[i-1, j-1];
//替换:考虑C[i-1,j-1],即在i-1,j-1的情况下已经得到最好值,并且新近考虑的i和j字符不相同,则需一次替换额外动作
//int candidate = C[i - 1, j - 1]+1;
int candidateMatRep;
if (char.Equals(originalStr[i - 1], targetStr[j - 1]))
{
candidateMatRep
= C[i - 1, j - 1];
}
else
{
candidateMatRep
= C[i - 1, j - 1] + 1;
}
//三者取最小代价
C[i, j] = Math.Min(Math.Min(candidateDel, candidateIns), candidateMatRep);
}
}
return C;
}
public List GetPossibleDesicion(int[,] C, int row, int col)
{
List
lo = new List();

for (int i = row, j = col; i > 0 || j > 0; )
{
if (C[i, j] == C[i - 1, j] + 1)//删除
{
lo.Add(
new OperationOnOriginalStr(Operation.Delete, i-1));
i
--;
}
else if (C[i, j] == C[i, j - 1] + 1) //插入
{
lo.Add(
new OperationOnOriginalStr(Operation.Insert, i-1, j-1));
j
--;
}
else if (C[i, j] == C[i - 1, j - 1])//匹配
{
lo.Add(
new OperationOnOriginalStr(Operation.Match, i-1,j-1));
i
--;
j
--;
}
else //替换
{
lo.Add(
new OperationOnOriginalStr(Operation.Replace, i-1, j-1));
i
--;
j
--;
}
}

return lo.Reverse().ToList();
}
}
public enum Operation
{
Delete,
Insert,
Replace,
Match
}
public class OperationOnOriginalStr
{
public OperationOnOriginalStr(Operation op, int aindex, int? bindex = null)
{
operation
= op;
AIndex
= aindex;
BIndex
= bindex;
}
public Operation operation { get; set; }
public int AIndex { get; set; }
public int? BIndex { get; set; }
}

调用方法如下:

            MinimumEditDistance med = new MinimumEditDistance();
var C = med.CalculateDistance(A, B);
var steps = med.GetPossibleDesicion(C, A.Length, B.Length);
steps.ForEach(s
=> Console.WriteLine("Operation:{0},A[{1}],B[{2}]", s.operation, s.AIndex, s.BIndex));

 

作者:Andy Zeng

欢迎任何形式的转载,但请务必注明出处。

http://www.cnblogs.com/andyzeng/p/3736012.html


推荐阅读
  • 我在尝试将组合框转换为具有自动完成功能时遇到了一个问题,即页面上的列表框也被转换成了自动完成下拉框,而不是保持原有的多选列表框形式。 ... [详细]
  • 本文探讨了Android系统中联系人数据库的设计,特别是AbstractContactsProvider类的作用与实现。文章提供了对源代码的详细分析,并解释了该类如何支持跨数据库操作及事务处理。源代码可从官方Android网站下载。 ... [详细]
  • Lua字符串1.字符串常见形式字符串或串(String)是由数字、字母、下划线组成的一串字符。Lua语言中字符串可以使用以下三种方式来表示:•单引号间的一串字符。 ... [详细]
  • 在AngularJS中,有时需要在表单内包含某些控件,但又不希望这些控件导致表单变为脏状态。例如,当用户对表单进行修改后,表单的$dirty属性将变为true,触发保存对话框。然而,对于一些导航或辅助功能控件,我们可能并不希望它们触发这种行为。 ... [详细]
  • 本文介绍了一种在 Android 开发中动态修改 strings.xml 文件中字符串值的有效方法。通过使用占位符,开发者可以在运行时根据需要填充具体的值,从而提高应用的灵活性和可维护性。 ... [详细]
  • 来自FallDream的博客,未经允许,请勿转载,谢谢。一天一套noi简直了.昨天勉强做完了noi2011今天教练又丢出来一套noi ... [详细]
  • 本文详细介绍了在PHP中如何获取和处理HTTP头部信息,包括通过cURL获取请求头信息、使用header函数发送响应头以及获取客户端HTTP头部的方法。同时,还探讨了PHP中$_SERVER变量的使用,以获取客户端和服务器的相关信息。 ... [详细]
  • java datarow_DataSet  DataTable DataRow 深入浅出
    本篇文章适合有一定的基础的人去查看,最好学习过一定net编程基础在来查看此文章。1.概念DataSet是ADO.NET的中心概念。可以把DataSet当成内存中的数据 ... [详细]
  • 使用 ModelAttribute 实现页面数据自动填充
    本文介绍了如何利用 Spring MVC 中的 ModelAttribute 注解,在页面跳转后自动填充表单数据。主要探讨了两种实现方法及其背后的原理。 ... [详细]
  • 本文详细介绍了如何使用Linux下的mysqlshow命令来查询MySQL数据库的相关信息,包括数据库、表以及字段的详情。通过本文的学习,读者可以掌握mysqlshow命令的基本语法及其常用选项。 ... [详细]
  • 本文介绍了如何使用Java编程语言实现凯撒密码的加密与解密功能。凯撒密码是一种替换式密码,通过将字母表中的每个字母向前或向后移动固定数量的位置来实现加密。 ... [详细]
  • 题面:P3178[HAOI2015]树上操作好像其他人都嫌这道题太容易了懒得讲,好吧那我讲。题解:第一个操作和第二个操作本质上是一样的&# ... [详细]
  • Java中List的forEach方法与字符串拼接的兼容性问题
    本文深入探讨了在Java中使用List的forEach方法时遇到的字符串拼接问题,提供了有效的解决方案及背后的原理分析,旨在帮助开发者更好地理解和解决此类问题。 ... [详细]
  • 本文介绍如何通过Java代码调用阿里云短信服务API来实现短信验证码的发送功能,包括必要的依赖添加和关键代码示例。 ... [详细]
  • 探讨多种方法来确定Java对象的实际类型,包括使用instanceof关键字、getClass()方法等。 ... [详细]
author-avatar
QueenieYam任嘉明
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有