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

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相对于关联权重的最大权重。最重公共(public)子序列(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

你需要构建的表会有这个。

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 的值。

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