当前位置：首页 > news >正文

【最长公共子序列】两行字符串，不交叉相连，最多连线

news 来源：原创 2024/5/7 8:22:35

连连看

题目：现将两个长度都为n的字符串str1, str2写在两行，用直线将两个单词中相同的字母进行连接。试求出在不出现连线交叉的情况下，最多可以画出多少根线max count

举例输入str1="ATM", str2="CAT",n=3,输出max_count=2

输入t1="BOOK str2="BOOL，n=4.输出max_count=3,分析见下图

自己的分析

分析草稿：

子串：必须连续

子序列：可以不连续

最长公共子序列参考博客

参考博客：

最长公共子序列(LCS)_梦想总是要不可及，是不是应该放弃的博客-CSDN博客_最长公共子序列

LCS 最长公共子序列 - WTSRUVF - 博客园

dp看终态就行就是看n的时候看n能有哪些状态推出来边界单独设置也没问题只不过就重复设置了 for循环里每个下标都遍历到了（ memset初始化置0

js代码

//导入包
var __readline = require('readline-sync')
__readline.setDefaultOptions({prompt: ''})
var read_line = __readline.prompt

//下面的代码是我们需要贴到赛码网编译器的

// 求最长公共子序列的长度
function LCS(m,n,str1, str2) {
    // var m = str1.length;
    // var n = str2.length;
    // 定义一维数组
    var dp = [];
    // dp维度(m+1)(n+1),由于0的位置空串的判断
    for (var i = 0; i <= m; i++) {
        // 将一维数组升级为二维数组
        dp[i] = [];
        for (var j = 0; j <= n; j++) {
            // 空串的情况
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
                // 还有继续向后判断的
                continue;
            }
            // str维度为 m n ,dp维度(m+1)(n+1)
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 取当前位置上或左的最大数
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // 最长公共子序列长度返回二维数组最后一个值
    // return dp[m][n];

    //输出其中一个最长子序列具体值
    var res = print_LCS(dp, str1, str2, m, n);
    return res;
}

// 打印输出其中一个最长子序列具体值
function print_LCS(dp, str1, str2, i, j) {
    if (i == 0 || j == 0) {
        return "";
    }
    if (str1[i - 1] == str2[j - 1]) {
        return print_LCS(dp, str1, str2, i - 1, j - 1) + str1[i - 1];
    } else if (dp[i][j - 1] > dp[i - 1][j]) {
        return print_LCS(dp, str1, str2, i, j - 1);
    } else {
        return print_LCS(dp, str1, str2, i - 1, j);
    }
}


// 处理输入输出
var line1 = read_line();
var num = line1.split(' ');
var m = parseInt(num[0]);
var n = parseInt(num[1]);

var line2 = read_line();
var str = line2.split(' ');
var str1 = str[0];
var str2 = str[1];

console.log("最长：",LCS(m,n,str1, str2));

相关参考

赛码网输入输出(js v8)问题并配置赛码网vscode本地环境__匀升的博客-CSDN博客_赛码网js输入输出
npm install readline-sync

py代码（多写了打印最长公共子序列的函数）

def LCS(str1,str2):
    m = len(str1)
    n = len(str2)
    dp = [[0 for _ in range(m + 1)] for _ in range (n + 1)]
    # print("inint_dp:",dp)
    for i in range(1 , m+1):
        for j in range (1 , n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    # print("lcs_dp:",dp)
    # return dp[m][n]

    res = print_LCS(dp,str1,str2,m,n)
    return res


def print_LCS(dp,str1,str2,i,j):
    # if(i==0)|(j==0):
    if(i==0)or(j==0):
        return ""
    if str1[i-1] == str2[j-1]:
        return print_LCS(dp,str1,str2,i-1,j-1) + str1[i-1]
    elif dp[i-1][j] > dp[i][j-1]:
        return print_LCS(dp,str1,str2,i-1,j)
    else:
        return print_LCS(dp,str1,str2,i,j-1)

# m,n = [x for x in input().strip().split()]
m,n = [int(i) for i in input().split(" ") ]  
# print(m,n)
str1 = input()
str2 = input()
# print(str1)
# print(str2)
print("LCS:",LCS(str1, str2))


# print("LCS:",LCS('abcd', 'bcde'))

其他

JS求最长公共子序列、最大公共子串、最大子段和 - 简书 (jianshu.com)

第一行第一列全为0

javascript 最长公共子序列_个人文章 - SegmentFault 思否

(77条消息) 动态规划最长公共子序列过程图解_Running07的博客-CSDN博客_最长公共子序列

打表打印：输出其中一个最长子序列或者所有的最长子序列，有区别

JS求最长公共子序列、最大公共子串、最大子段和 - 简书 (jianshu.com)

子串待看

py

Python实现最长公共子序列搜索 - 知乎