为多个序列最长公共子 [英] Longest Common Subsequence for Multiple Sequences

问题描述

我已经做了一堆的研究寻找最长为M = 2的序列，但我试图找出如何做到这一点的M> = 2的序列。我被指定N和M：M序列，具有N个独特的元素。 N是集合{1 - N}。我曾经想过，动态规划方法，但我仍然困惑，如何真正将它。

I have done a bunch of research for finding the longest for M=2 sequences, but I am trying to figure out how to do it for M>=2 sequences. I am being given N and M: M sequences, with N unique elements. N is the set of {1 - N}. I have thought about the dynamic programming approach, but I am still confused as to how to actually incorporate it.

例输入
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

Example input
5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

这里的最大序列可被看作是
5 3 1

The max sequence here can be seen to be
5 3 1

预计产量
长度= 3

Expected output
Length = 3

推荐答案

一个简单的想法。

对于每个编号我的 1 和 N ，计算最长的子序列，其中最后一个数字是我。 （我们称之为 A [1] ）

For each number i between 1 and N, calculate the longest subsequence where the last number is i. (Let's call it a[i])

要做到这一点，我们将遍历号我从开始的第一个序列结束。如果 A [1]＆GT; 1 ，然后还有一些Ĵ，使得每个序列中谈到之前我。< BR> 现在，我们可以只检查Ĵ的所有可能值及（如previous条件成立）做 A [1] = MAX（A [1 ]，一个[J] + 1）。

To do that, we'll iterate over numbers i in the first sequence from start to end. If a[i] > 1, then there's number j such that in each sequence it comes before i.
Now we can just check all possible values of j and (if previous condition holds) do a[i] = max(a[i], a[j] + 1).

随着最后一位​​，因为Ĵ来之前我在第一个序列，这意味着一[J] 已计算。

As the last bit, because j comes before i in first sequence, it means a[j] is already calculated.

for each i in first_sequence
    // for the OP's example, 'i' would take values [5, 3, 4, 1, 2], in this order
    a[i] = 1;
    for each j in 1..N
        if j is before i in each sequence
            a[i] = max(a[i], a[j] + 1)
        end
    end
end

这是 O（N ^ 2 * M），如果计算位置矩阵事先。

It's O(N^2*M), if you calculate matrix of positions beforehand.

这篇关于为多个序列最长公共子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！