基于k值的多字符单元最长公共子序列（LCS）实现方法问询

核心思路 #

• 第一步：序列预处理：将两个输入字符串按固定长度k切分为不重叠的连续单元，每个单元内字符排序生成唯一标识，消除字符顺序的影响，满足EF == FE的相等判定要求
• 第二步：标准LCS动态规划求解：把预处理后的单元标识序列作为输入，用经典LCS的DP算法计算最长公共子序列的单元数，就是要求的结果

边界条件说明 #

• 若k≤0，直接返回0
• 若单条字符串总长度不足k，返回0
• 字符串长度不是k的整数倍时，末尾不足k的片段直接丢弃

代码实现（Python） #

def k_unit_lcs(k: int, s1: str, s2: str) -> int:
    # 预处理函数：切分+单元归一化
    def preprocess(s: str, k: int) -> list[str]:
        if k <= 0 or len(s) < k:
            return []
        units = []
        for i in range(0, len(s) - k + 1, k):
            unit = s[i:i+k]
            # 单元内字符排序生成唯一匹配key
            norm_unit = ''.join(sorted(unit))
            units.append(norm_unit)
        return units
    
    a = preprocess(s1, k)
    b = preprocess(s2, k)
    m, n = len(a), len(b)
    # 初始化DP表
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# 测试示例1
k1 = 3
s1_1 = "AAABBBCCCDDDEEE"
s2_1 = "AAACCCBBBDDDEEE"
print(k_unit_lcs(k1, s1_1, s2_1)) # 输出4，符合示例要求

# 测试示例2
k2 = 2
s1_2 = "EEDDFFAABBCC"
s2_2 = "AACCDDEEBBFF"
print(k_unit_lcs(k2, s1_2, s2_2)) # 输出2，符合示例要求

扩展：回溯获取具体公共子序列 #

如果需要得到示例中具体的公共子序列字符串，可以在DP表计算完成后新增回溯逻辑：

def get_lcs_string(k: int, s1: str, s2: str) -> str:
    def preprocess(s: str, k: int) -> tuple[list[str], list[str]]:
        if k <=0 or len(s)<k:
            return [], []
        norm_units = []
        raw_units = []
        for i in range(0, len(s)-k+1, k):
            unit = s[i:i+k]
            raw_units.append(unit)
            norm_unit = ''.join(sorted(unit))
            norm_units.append(norm_unit)
        return norm_units, raw_units
    
    a, raw_a = preprocess(s1, k)
    b, _ = preprocess(s2, k)
    m, n = len(a), len(b)
    # 计算DP表
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] +1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    # 回溯匹配路径
    i, j = m, n
    res_units = []
    while i>0 and j>0:
        if a[i-1] == b[j-1]:
            res_units.append(raw_a[i-1])
            i -=1
            j -=1
        elif dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            # 相等时选不同分支可得到不同的合法公共子序列
            j -=1
    # 反转得到正序后拼接为字符串
    return ''.join(reversed(res_units))

内容的提问来源于stack exchange，提问作者trab