Реализовать алгоритм определения наибольшей общей подпоследовательности двух строк.

Наибольшая общая подпоследовательность

Задание: Реализовать алгоритм определения наибольшей общей подпоследовательности двух строк.

def lcs(X, Y):
    m = len(X)
    n = len(Y)
    L = [[0] * (n+1) for i in range(m+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])
 
    index = L[m][n]
    lcs_str = [""] * (index+1)
    lcs_str[index] = ""
 
    i = m
    j = n
    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs_str[index-1] = X[i-1]
            i-=1
            j-=1
            index-=1
        elif L[i-1][j] > L[i][j-1]:
            i -= 1
        else:
            j -= 1
 
    return ''.join(lcs_str)

# Пример использования
X = "AGGTAB"
Y = "GXTXAYB"
result = lcs(X, Y)
print("LCS of", X, "and", Y, "is", result)

Результат выполнения кода

LCS of AGGTAB and GXTXAYB is GTAB

Этот код реализует алгоритм нахождения наибольшей общей подпоследовательности для двух данных строк. Результат показывает, что такая последовательность для строк "AGGTAB" и "GXTXAYB" — "GTAB".

Категория: Практические упражнения Python | Добавил: Admin (03.05.2024)
Просмотров: 19 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *: