python 如何获取两个span的最长公共子序列（包含中文和英文版本）

目录

问题描述

代码实现

中文字符串：

英文字符串：

问题描述

给定两个字符串，如何返回两个字符串的最长公共子序列。

代码实现

中文字符串：

def longest_chinese_common_subsequence(str1, str2):
    # 返回联系的最长公共子序列
    m, n = len(str1), len(str2)

    # 创建一个二维数组来保存子问题的解
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 记录最长连续子序列的长度和结束位置
    max_length = 0
    end_position = 0

    # 填充数组，使用动态规划算法
    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
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_position = i
            else:
                dp[i][j] = 0

    # 获取最长连续子序列
    start_position = end_position - max_length
    if max_length == 0:
        return None
    else:
        longest_subsequence = str1[start_position:end_position]
        return longest_subsequence

英文字符串：

def longest_english_common_subsequence(str1, str2):
    str1 = str1.split()
    str2 = str2.split()
    m, n = len(str1), len(str2)

    # 创建一个二维数组来存储最长公共子序列的长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 记录最长公共子序列的结束位置和长度
    max_length = 0
    end_position = 0

    # 填充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
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_position = i - 1
            else:
                dp[i][j] = 0

    if max_length == 0:
        return None
    
    # 通过最长公共子序列的结束位置和长度得到最长公共子序列
    lcs = str1[end_position - max_length + 1: end_position + 1]

    # 将结果输出
    return ' '.join(lcs)