是否有任何算法可以解决每个字符具有不同权重的最长公共子序列问题？

Question

我正在寻找一种算法来解决具有以下条件的两个字符串的 LCS 问题：

每个字符串由英文字符组成，每个字符都有一个权重。例如：

sequence 1 (S1): "ABBCD" with weights [1, 2, 4, 1, 3]

sequence 2 (S2): "TBDC" with weights [7, 5, 1, 2]

假设MW(s, S)定义为字符串S中的子序列s相对于关联权重的最大权重。最重公共子序列（HCS）定义为：

HCS = argmin(MW(s, S1), MW(s, S2))

算法输出应该是HCS在字符串和权重上的索引。在这种情况下，索引将是：

I_S1 = [2, 4] --> MW("BD", "ABBCD") = 7

I_S2 = [1, 2] --> MW("BD", "TBDC") = 6

因此HCS = "BD", and weight = min(MW(s, S1), MW(s, S2)) = 6.

Answer 1

你需要搭建的table会有这个

for each position in sequence 1
    for each position in sequence 2
        for each extreme pair of (weight1, weight2)
            (last_position1, last_position2)

其中极端对是指不可能找到该点的子序列，其在序列 1 和序列 2 中的权重都 >=，并且至少有一个 >.

可能存在多个极端对，其中一个序列高于另一个。

规则是，在 (i, -1) 或 (-1, j) 位置，唯一的极端对是权重为 0 的空集。在任何其他位置，我们合并 (i-1, j) 的极端对和 (i, j-1)。然后，如果 seq1[i] = seq2[j]，则将选项添加到 (i-1, j-1)，然后在相应的子序列中包含 i 和 j。（因此将 weight1[i] 和 weight2[j] 添加到权重然后进行合并。）

对于该合并，您可以按 weight1 升序排序，前面两个点的所有极值，然后丢弃所有 weight2 小于或等于最佳 weight2 的那些顺序。

当你到达终点时，你可以找到具有最高最小值的极端对，这就是你的答案。然后您可以返回数据结构以找到有问题的子序列。

是否有任何算法可以解决每个字符具有不同权重的最长公共子序列问题？

Is there any algorithm to address the longest common subsequence problem with different weights for each character?

algorithm

dynamic-programming

lcs