`

最长公共子序列 与 最长子序列 (C++实现)

 
阅读更多
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from stdin).

#include <iostream>
using namespace std;

int check_in_list(int l[], int n, int e) {
    for(int i = 0; i < n; i++) {
        if(l[i] == e) return 1;
    }
    return 0;
}

// 最长公共子序列长度
int max_common_seq(int l1[], int m, int l2[], int n) {
    if (m==0 || n==0) return 0;
    if (m==1) return check_in_list(l2, n, l1[0]);
    if (n==1) return check_in_list(l1, m, l2[0]);
    
    int dp[100][100] = {0};
    
    // first line
    int temp = check_in_list(l1, m, l2[0]);
    if (temp) for(int i = 0; i < m; i++, dp[i][0] = temp);
    // first row
    temp = check_in_list(l2, n, l1[0]);
    if (temp) for(int j = 0; j < n; j++, dp[0][j] = temp);
    
    int ms = 0;
    
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            if(l1[i] == l2[j]) dp[i][j] = dp[i-1][j-1]+1;
            else 
            dp[i][j] = max(
                dp[i][j-1],
                dp[i-1][j]
            );
            ms =  max(ms, dp[i][j]);
        }
    }
    return ms;
}
// 最长子序列长度
int max_seq(int l[], int n) {
    if (n <= 1) return n;
    int maxs = 0; 
    int lasts = 1;
    for (int i = 1; i < n; i++) {
        lasts = l[i] >= l[i-1] ? lasts+1 : 1;
        maxs = max(maxs, lasts);
    }
    return maxs;
}

int main() {
    // 测试最长子序列长度
    int l[] = {1, 3, 4, 2, 3, 1, 3, 2, 5, 6, 9, 11};
    cout<<max_seq(l, 11)<<endl;
    
    // 测试最长公共子序列长度
    int l1[] = {1, 4, 5, 7, 9, 10, 13};
    int l2[] = {1, 5, 7, 10, 8, 10, 13, 14};
    cout<<max_common_seq(l1, 7, l2, 8)<<endl;
    
    return 0;
}

 

分享到:
评论

相关推荐

    最长公共子序列MFC实现

    如果它是源代码,我们可以期待找到一个或多个C++文件,里面包含使用MFC编写的函数或类,用于计算两个序列的最长公共子序列。如果它是测试数据,可能包含一些文本文件,每行代表一个序列,用于验证算法的正确性。 总...

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

    设`L[i][j]`表示`X[1...i]`与`Y[1...j]`的最长公共子序列的长度,则状态转移方程为: - 如果`xi == yj`,则`L[i][j] = L[i-1][j-1] + 1` - 如果`xi != yj`,则`L[i][j] = max(L[i-1][j], L[i][j-1])` 这里的`L[i]...

    C++实现 最长公共子序列

    在计算机科学领域,最长公共子序列(Longest Common Subsequence, LCS)问题是一个经典的问题,主要涉及算法设计和分析。该问题旨在找到两个给定序列的最长子序列,这个子序列不必连续,但必须保持原序列的相对顺序...

    c c++最长公共子序列 实现算法

    C++实现的LCS算法利用了动态规划,有效地解决了两个字符串之间的最长公共子序列问题。这个算法的时间复杂度是O(m * n),其中m和n分别是输入字符串的长度。它在实际应用中,如生物信息学中的序列比对、文本编辑器的...

    最长公共子序列c++

    最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要...通过C++实现,我们可以高效地找到两个字符串的最长公共子序列,这对于文本分析、生物信息学等领域都有实际的应用价值。

    最长公共子序列问题LCS

    如果最后一个元素不相等,那么最长公共子序列将是两个序列去掉最后一个元素后各自与对方的最长公共子序列中的较长者。 解决LCS问题,通常采用动态规划的方法。动态规划是一种自底向上的方法,通过构建一个二维数组...

    动态规划方法求解最长公共子序列代码

    本主题聚焦于使用动态规划方法求解最长公共子序列问题,并通过C++语言实现代码进行阐述。 最长公共子序列问题描述如下:给定两个字符串S和T,找出它们的最长子序列,这个子序列不必是连续的,但必须保持原顺序。...

    c++最长公共子序列问题LCSLength

    最长公共子序列(Longest Common Subsequence,LCS)问题是计算机科学中一个经典的字符串处理问题,它在序列比对、代码优化、数据恢复等多个领域有广泛的应用。在C++编程中,解决这个问题通常采用动态规划的方法。...

    最长公共子序列程序和实验报告

    最长公共子序列(Longest Common Subsequence,简称LCS)是计算机科学中一种经典的字符串问题,广泛应用于文本比较、生物信息学等领域。本实验报告主要围绕LCS算法的实现及其实验过程进行深入探讨。 首先,我们要...

    最长公共子序列

    通过深入理解LCS问题,我们可以扩展这个基本实现,例如,找出具体的最长公共子序列,或者处理多个序列的LCS问题。同时,也可以探讨其他算法,如使用回溯法或者启发式方法来解决这个问题,尽管这些方法可能在效率上...

    最长公共子序列的C++代码,可以正常运行,有注释。

    给定两个序列X和Y,寻找这两个序列的最长公共子序列是指在X和Y中同时出现的最长子序列。例如,如果X是"ABCDGH",Y是"AEDFHR",那么它们的最长公共子序列是"ADH"。 在这个代码中,我们使用C++语言来实现LCS算法。这...

    最长公共子序列_动态规划

    最长公共子序列(Longest Common Subsequence,LCS)是计算机科学中一种经典的字符串问题,主要涉及算法设计与分析,特别是在动态规划领域的应用。在这个问题中,我们需要找到两个或多个字符串之间的最长子序列,这...

    最长公共子序列算法试验报告

    【最长公共子序列算法】 最长公共子序列(Longest Common Subsequence, ...在这个实验中,我们学习了如何运用动态规划来找到两个字符串的最长公共子序列,加深了对动态规划思想的理解,并通过实际编程实现了这一过程。

    LCS最长公共子序列(输出一条最长子序列)

    《LCS最长公共子序列(输出一条最长子序列)》 在计算机科学中,最长公共子序列(Longest Common Subsequence, LCS)问题是一个经典的算法问题,它涉及到序列的比较和匹配。这个问题的目标是找到两个给定序列的最...

    最长公共子序列--动态规划法实验

    在提供的源代码"最长公共子序列.cpp"中,可以看到具体的C++实现细节。代码可能会包含以下部分: - 函数声明和定义:通常会有一个函数如`int longestCommonSubsequence(string s1, string s2)`用于计算LCS长度。 - ...

    最长公共子序列(LCS)算法源代码和实验报告

    我们可以使用二维数组L[i][j]来存储两个序列X和Y前i个字符与前j个字符的最长公共子序列的长度。基本的递推关系如下: 1. 如果X[i-1] = Y[j-1],则L[i][j] = L[i-1][j-1] + 1,表示在当前字符匹配的情况下,最长公共...

    最长公共子序列问题 动态规划法.cpp.rar

    最长公共子序列(Longest Common Subsequence,LCS)问题是计算机科学中一个经典的字符串处理问题,它寻找两个序列之间的最长子序列,这个子序列不必连续但必须保持原序列的相对顺序。在本例中,提供的文件是使用C++...

    动态规划最长公共子序列

    动态规划最长公共子序列(Longest Common Subsequence, LCS)是计算机科学中一个经典的问题,主要涉及算法设计和分析。在本场景中,我们聚焦于使用动态规划方法解决这一问题。最长公共子序列是指两个或多个序列中,...

    最长公共子序列一行最优值

    c++最长公共子序列一行最优值最长公共子序列(LCS)是一个在一个序列集合中(通常为两个序列)用来查找所有序列中最长子序列的问题。一个数列 ,如果分别是两个或多个已知数列的子序列,且是所有符合此条件序列中...

Global site tag (gtag.js) - Google Analytics