Рубрики

Программа Python для самой длинной общей подпоследовательности

Постановка задачи LCS: Учитывая две последовательности, найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность — это последовательность, которая появляется в том же относительном порядке, но не обязательно является смежной. Например, «abc», «abg», «bdf», «aeg», «acefg» и т. Д. Являются подпоследовательностями «abcdefg». Таким образом, строка длиной n имеет 2 ^ n различных возможных подпоследовательностей.

Это классическая проблема информатики, основа diff (программа сравнения файлов, которая выводит различия между двумя файлами) и имеет приложения в биоинформатике.

Примеры:
LCS для входных последовательностей «ABCDGH» и «AEDFHR» — это «ADH» длины 3.
LCS для входных последовательностей «AGGTAB» и «GXTXAYB» — это «GTAB» длины 4.

Пусть входными последовательностями являются X [0..m-1] и Y [0..n-1] длин m и n соответственно. И пусть L (X [0..m-1], Y [0..n-1]) будет длиной LCS двух последовательностей X и Y. Ниже приводится рекурсивное определение L (X [0 .. m-1], Y [0..n-1]).

Если последние символы обеих последовательностей совпадают (или X [m-1] == Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = 1 + L (X [0..m-2], Y [0..n-2])

Если последние символы обеих последовательностей не совпадают (или X [m-1]! = Y [n-1]), то
L (X [0..m-1], Y [0..n-1]) = MAX (L (X [0..m-2], Y [0..n-1]), L ( X [0..m-1], Y [0..n-2])

# Наивная рекурсивная реализация проблемы LCS на Python

  

def lcs(X, Y, m, n):

  

    if m == 0 or n == 0:

       return 0;

    elif X[m-1] == Y[n-1]:

       return 1 + lcs(X, Y, m-1, n-1);

    else:

       return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

  

  
# Драйвер программы для проверки вышеуказанной функции

X = "AGGTAB"

Y = "GXTXAYB"

print "Length of LCS is ", lcs(X, Y, len(X), len(Y))

Выход:

Length of LCS is  4

Ниже приведена табличная реализация проблемы LCS.

# Динамическое программирование реализации задачи LCS

  

def lcs(X, Y):

    # найти длину строк

    m = len(X)

    n = len(Y)

  

    # объявление массива для хранения значений dp

    L = [[None]*(n + 1) for i in xrange(m + 1)]

  

    "" "Следующими шагами создайте L [m + 1] [n + 1] снизу вверх

    Примечание: L [i] [j] содержит длину LCS из X [0..i-1]

    и Y [0..j-1] "" "

    for i in range(m + 1):

        for j in range(n + 1):

            if i == 0 or j == 0 :

                L[i][j] = 0

            elif X[i-1] == Y[j-1]:

                L[i][j] = L[i-1][j-1]+1

            else:

                L[i][j] = max(L[i-1][j], L[i][j-1])

  

    # L [m] [n] содержит длину LCS из X [0..n-1] & Y [0..m-1]

    return L[m][n]

# конец функции lcs

  

  
# Драйвер программы для проверки вышеуказанной функции

X = "AGGTAB"

Y = "GXTXAYB"

print "Length of LCS is ", lcs(X, Y)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

Выход:

Length of LCS is  4

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 4 (Longest Common Subsequence) для более подробной информации!

Рекомендуемые посты:

Программа Python для самой длинной общей подпоследовательности

0.00 (0%) 0 votes