`
kmplayer
  • 浏览: 508890 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

返回两个字符串最长公共子序列.

J# 
阅读更多
1,解决:一个简单的动态规划:
string a,b;
dp[0][_] = dp[_][0] = 0;
dp[i][j] = a[i]==b[j]?   dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);

2,实例代码:
#include<iostream>
using namespace std;

const int N=100;
int dp[N][N];

//该函数只是得到最大公共长度
int maxSubSquence(const char* a,const char* b)
{
    memset(dp,0,sizeof(dp));
    int m=strlen(a);
    int n=strlen(b);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
                dp[i][j]=dp[i-1][j]>dp[i][j-1]? dp[i-1][j]:dp[i][j-1];
        }
    return dp[m][n];
}


//可以将最长序列返回
char re[N];
int maxSubSquence2(const char* a,const char* b)
{
    int s[N][N];
    memset(dp,0,sizeof(dp));
    int m=strlen(a);
    int n=strlen(b);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
                s[i][j]=1;
            }
            else
                dp[i][j]=dp[i-1][j]>dp[i][j-1]? (s[i][j]=2,dp[i-1][j]):(s[i][j]=3,dp[i][j-1]);
        }
    int len=dp[m][n];
    re[len]='\0';
    //根据s[i][j]的状态提取公共子序列
    for(int i=m,j=n;i>0&&j>0;)
    {
        switch(s[i][j])
        {
        case 1:
            re[--len]=a[i-1];i--;j--;
            break;
        case 2:
            i--;
            break;
        case 3:
            j--;
            break;
        }
    }
    return dp[m][n];
}

int main()
{
    const char* a="xyxzyxyzzy";
    const char* b="xzyzxyzxyzxy";
    cout<<maxSubSquence2(a,b)<<endl;
    cout<<re<<endl;
    return 0;
}
分享到:
评论

相关推荐

    求两个字符串的最长公共子序列.pdf

    最长公共子序列算法 本文将详细介绍最长公共子序列(Longest Common Subsequence,LCS)算法的概念、原理和实现。LCS 是一种经典的字符串处理算法,广泛应用于自然语言处理、数据压缩、生物信息学等领域。 什么是...

    公共子序列-查找两个字符序列的所有公共子序列

    LCS算法的目标是找到两个字符串的最长公共子序列。其基本思想是构建一个二维数组,其中的每个元素代表对应位置的两个字符是否构成公共子序列。通过遍历这个二维数组,我们可以逐步推导出最长公共子序列。 具体步骤...

    使用Java实现的计算两字符串相似度+最长公共子序列.zip

    在计算机科学领域,字符串处理是常见的一类任务,其中计算两个字符串的相似度以及找到它们的最长公共子序列(Longest Common Subsequence, LCS)是一个经典的问题。本篇将深入探讨这个问题,以及如何使用Java来解决...

    求字符串的最长公共子序列

    递归解法的基本思路是定义一个函数,该函数接收两个字符串作为参数,返回它们的LCS长度。递归关系可以这样描述:如果两个字符串为空,那么它们的LCS长度为0;如果其中一个字符串为空,另一个非空,则LCS长度等于非空...

    C++求最长公共子序列

    ### C++实现最长公共子序列算法详解 在深入解析给定代码之前,我们先来了解一下“最长公共子序列”(Longest Common Subsequence,简称LCS)的基本概念及其在计算机科学中的应用。LCS问题是一种典型的动态规划问题...

    算法题示例-最长公共子序列.rar

    给定两个字符串 text1 和 text2,找到这两个字符串的最长公共子序列(LCS)的长度。一个字符串的子序列是指这样一个字符串:它通过删除原字符串中的某些(也可以不删除)字符而不改变剩余字符的相对顺序得到。 示例...

    最长公共子序列.pdf

    这里,我们用`L(m,n)`表示两个字符串`X`和`Y`的前`m`个字符与前`n`个字符的最长公共子序列的长度。 算法分析分为以下三个情况: 1. 如果`xm=yn`,即两个字符串在当前位置的字符相等,那么`zk`可以设置为`xm=yn`,...

    最长公共子序列.(C语言编写) 算法

    最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中一种经典的字符串问题,它在比较两个或多个序列时寻找它们之间的最长相同部分,但这个相同部分不需要连续。这个问题在许多领域都有应用,比如生物...

    查询两个字符串的最长公共子序列

    利用指针来查询两个字符串的最长公共子序列,并输出的算法。

    Python求两个字符串最长公共子序列代码实例

    【Python求两个字符串最长公共子序列】 在编程领域,字符串操作是常见任务之一,而寻找两个字符串的最长公共子序列(LCS)是其中的一个经典问题。LCS是指两个字符串中都出现过的最长的连续子序列,但不考虑字符在...

    求两个字符串的最长公共字串

    - 函数`LCS`接受两个字符串参数,并返回它们的最长公共子串。 - 初始化变量`lenLeft`和`lenRight`分别存储输入字符串的长度。 - 创建字符数组`c`用于记录最长公共子串的长度。 - 遍历`left`字符串中的每个字符,对于...

    最长公共子序列.txt

    Problem Description 给你一个序列X和另一个序列Z,当Z中的所有元素都在X中...对于每组输入,输出两个字符串的最长公共子序列的长度。 Sample Input abcfbc abfcab programming contest abcd mnp Sample Output 4 2 0

    最长公共子序列

    ### 最长公共子序列(LCS):深入解析与实现 #### 一、概念与应用场景 最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一个重要的算法问题,它主要应用于字符串比较、文本编辑、生物信息学...

    最长公共子序列的动态规划算法

    总结来说,最长公共子序列问题是一个典型的动态规划问题,通过使用C#编程语言,我们可以有效地求解两个字符串的最长公共子序列。这种算法在文本比较、生物信息学、软件工程等领域有广泛应用。理解并能实现这种算法...

    最长公共子序列问题动态规划解决,二个或者三个字符串的

    哈工大算法实验二,最长公共子序列问题,动态规划解决LCS ...3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!均为自己所做,正确运行。报告中还有用Excel表分析了算法的性能

    C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...

    最长公共子序列算法C#实现

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的问题,主要应用于比较和分析两个或多个序列的相似性。在这个问题中,目标是找到两个序列的最长子序列,这个子序列不需要在原序列中...

    最长公共子序列算法设计与实现(c++).zip

    算法工程项目问题描述: 【题目】 动态规划思维训练——最长公共子序列算法的设计与实现 给定两个序列X={X1, X2,···,Xm}和...字符串Y:{ABCBDAB},则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA

Global site tag (gtag.js) - Google Analytics