C#,最大公共子序列(LCS,Longest Common Subsequences)的算法与源代码

本文主要是介绍C#,最大公共子序列(LCS,Longest Common Subsequences)的算法与源代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 最大公共子序列

最长的常见子序列问题是寻找两个给定字符串中存在的最长序列。

最大公共子序列算法,常用于犯罪鉴定、亲子鉴定等等的 DNA 比对。

1.1 子序列

让我们考虑一个序列S=<s1,s2,s3,s4,…,sn>。

一个序列Z=<z1,z2,z3,z4,…,zm>在S上被称为S的子序列,当且仅当它可以从某些元素的S删除中派生出来时。

1.2 公共子序列

假设X和Y是有限元素集上的两个序列。如果Z是X和Y的子序列,我们可以说Z是X和Y的公共子序列。

1.3 最长公共子序列

如果给定一组序列,则最长公共子序列问题是找到所有序列中具有最大长度的公共子序列。

最长的常见子序列问题是一个经典的计算机科学问题,是diff实用程序等数据比较程序的基础,在生物信息学中有应用。它还被SVN和Git等版本控制系统广泛用于协调对受版本控制的文件集合所做的多个更改。

2 递归算法源程序

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class StringSearch
    {
        /// <summary>
        /// 两个字符串的最大公共子字符串
        /// </summary>
        /// <param name="X"></param>
        /// <param name="Y"></param>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int LCS_Solve(string X, string Y, int m, int n)
        {
            if (m == 0 || n == 0)
            {
                return 0;
            }
            if (X[m - 1] == Y[n - 1])
            {
                return 1 + LCS_Solve(X, Y, m - 1, n - 1);
            }
            else
            {
                return Math.Max(LCS_Solve(X, Y, m, n - 1), LCS_Solve(X, Y, m - 1, n));
            }
        }
    }
}
 

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class StringSearch{/// <summary>/// 两个字符串的最大公共子字符串/// </summary>/// <param name="X"></param>/// <param name="Y"></param>/// <param name="m"></param>/// <param name="n"></param>/// <returns></returns>public static int LCS_Solve(string X, string Y, int m, int n){if (m == 0 || n == 0){return 0;}if (X[m - 1] == Y[n - 1]){return 1 + LCS_Solve(X, Y, m - 1, n - 1);}else{return Math.Max(LCS_Solve(X, Y, m, n - 1), LCS_Solve(X, Y, m - 1, n));}}}
}

3 非递归算法源程序

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
    public static partial class StringSearch
    {
        /// <summary>
        /// 计算两个字符串的最大公共子字符串
        /// </summary>
        /// <param name="X"></param>
        /// <param name="Y"></param>
        /// <returns></returns>
        public static int LCS_Solve(string X, string Y)
        {
            int m = X.Length;
            int n = Y.Length;
            int[,] LengthArray = new int[m + 1, n + 1];

            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        LengthArray[i, j] = 0;
                    }
                    else if (X[i - 1] == Y[j - 1])
                    {
                        LengthArray[i, j] = LengthArray[i - 1, j - 1] + 1;
                    }
                    else
                    {
                        LengthArray[i, j] = Math.Max(LengthArray[i - 1, j], LengthArray[i, j - 1]);
                    }
                }
            }
            return LengthArray[m, n];
        }
    }
}

——————————————————————————

POWER BY TRUFFER.CN 50018.COM

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class StringSearch{/// <summary>/// 计算两个字符串的最大公共子字符串/// </summary>/// <param name="X"></param>/// <param name="Y"></param>/// <returns></returns>public static int LCS_Solve(string X, string Y){int m = X.Length;int n = Y.Length;int[,] LengthArray = new int[m + 1, n + 1];for (int i = 0; i <= m; i++){for (int j = 0; j <= n; j++){if (i == 0 || j == 0){LengthArray[i, j] = 0;}else if (X[i - 1] == Y[j - 1]){LengthArray[i, j] = LengthArray[i - 1, j - 1] + 1;}else{LengthArray[i, j] = Math.Max(LengthArray[i - 1, j], LengthArray[i, j - 1]);}}}return LengthArray[m, n];}}
}

这篇关于C#,最大公共子序列(LCS,Longest Common Subsequences)的算法与源代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/701900

相关文章

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

详解C#如何提取PDF文档中的图片

《详解C#如何提取PDF文档中的图片》提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使用,下面我们就来看看如何使用C#通过代码从PDF文档中提取图片吧... 当 PDF 文件中包含有价值的图片,如艺术画作、设计素材、报告图表等,提取图片可以将这些图像资源进行单独保存,方便后续在不同的项目中使

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时