Самая длинная общая подпоследовательность для нескольких последовательностей

Question

Я провел множество исследований, чтобы найти самые длинные для М = 2 последовательностей, но я пытаюсь выяснить, как это сделать для М ≥ 2 последовательностей

Мне дают N и M: M последовательностей с N уникальными элементами. N является множеством {1 - N}. Я думал о подходе динамического программирования, но я все еще не уверен, как на самом деле включить его.

Пример ввода

5 3
5 3 4 1 2
2 5 4 3 1
5 2 3 1 4

Максимальная последовательность здесь может быть

5 3 1

Ожидаемый результат

Length = 3

Answer 1

Простая идея.

Для каждого числа i между 1 и N вычислите самую длинную подпоследовательность, где последнее число равно i.(Давайте назовем это a[i])

Для этого мы будем перебирать числа i в первой последовательности от начала до конца.Если a[i] > 1, то существует число j, такое, что в каждой последовательности оно предшествует i.
Теперь мы можем просто проверить все возможные значения j и (если выполняется предыдущее условие) выполнить a[i] = max(a[i], a[j] + 1).

В качестве последнего бита, поскольку j предшествует i в первой последовательности, это означает, что a[j] уже вычислено.

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), если вычислитьматрица позиций заранее.

Answer 2

Поскольку у вас есть уникальные элементы, ответ @Nikita Rybak - один из них, но поскольку вы упомянули динамическое программирование, вот как вы будете использовать DP, если у вас более двух последовательностей:

dp[i, j, k] = length of longest common subsequence considering the prefixes
              a[1..i], b[1..j], c[1..k].


dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if a[i] = b[j] = c[k]
            = max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise

Чтобы вернуть фактическую подпоследовательность, используйте рекурсивную функцию, которая начинается с dp[a.Length, b.Length, c.Length] и в основном обращает вышеуказанные формулы: если три элемента равны, вернитесь к dp[a.Length - 1, b.Length - 1, c.Length - 1] и напечатайте символ.Если нет, вернитесь назад в соответствии с максимальным значением из вышеуказанных значений.

Answer 3

Вы можете посмотреть статью " Разработка нового детерминированного алгоритма для нахождения общей подпоследовательности ДНК ".Вы можете использовать этот алгоритм для построения DAG (стр. 8, рисунок 5).Из DAG прочитайте самые большие общие отличительные подпоследовательности.Затем попробуйте использовать подход динамического программирования, используя значение M, чтобы решить, сколько DAG вам нужно построить для каждой последовательности.В основном используйте эти подпоследовательности в качестве ключа и сохраните соответствующие порядковые номера там, где они найдены, а затем попытайтесь найти наибольшую подпоследовательность (которая может быть больше 1).