Tablica wspólnych podciągów

Najdłuższy wspólny podciąg - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

**Najdłuższy wspólny podciąg** (NWP, ang. LCS) dwóch napisów to najdłuższy napis, który jest podciągiem obu (litery w tej kolejności, z przerwami). `L[i][j]` to długość NWP pierwszych `i` liter napisu `a` i pierwszych `j` liter `b`. Gdy ostatnie litery są równe, `L[i][j] = L[i-1][j-1] + 1`, w przeciwnym razie `max(L[i-1][j], L[i][j-1])`.

a, b = "KAJAKI", "ALPAKI"
L = [[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]:
            L[i][j] = L[i - 1][j - 1] + 1
        else:
            L[i][j] = max(L[i - 1][j], L[i][j - 1])
print("   ", "  ".join(b))
for i in range(1, len(a) + 1):
    print(a[i - 1], L[i][1:])
print("długość NWP:", L[len(a)][len(b)])

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

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.