Najdłuższy wspólny podciąg

Programowanie dynamiczne - Algorytmy: zakres rozszerzony (Python)

**Najdłuższy wspólny podciąg** (NWP) dwóch napisów to najdłuższy ciąg znaków, który występuje w obu w tej samej kolejności (niekoniecznie obok siebie). `table[i][j]` to długość NWP początków napisów o długościach i oraz j. Jeśli ostatnie znaki są równe, wynik rośnie o 1 względem `table[i-1][j-1]`, a jeśli nie, bierzemy lepszy z dwóch sąsiednich wyników. Na koniec odtwarzamy sam podciąg, idąc od końca tablicy.

a = "INFORMATYKA"
b = "MATEMATYKA"
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
    for j in range(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            table[i][j] = table[i - 1][j - 1] + 1
        else:
            table[i][j] = max(table[i - 1][j], table[i][j - 1])
result = ""
i, j = len(a), len(b)
while i > 0 and j > 0:
    if a[i - 1] == b[j - 1]:
        result = a[i - 1] + result
        i -= 1
        j -= 1
    elif table[i - 1][j] >= table[i][j - 1]:
        i -= 1
    else:
        j -= 1
print("długość NWP:", table[len(a)][len(b)])
print("NWP:", result)

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.