Längste gemeinsame Teilsequenz in Python

1. Verwenden Sie die naive Methode, um die längste gemeinsame Teilsequenz in Python zu finden
2. Verwenden Sie die dynamische Programmierung, um die längste gemeinsame Teilsequenz in Python zu finden

Eine Untersequenz ist eine Sequenz, die aus den gegebenen Sequenzen erhalten wird, nachdem einige oder keine Zeichen entfernt wurden, ohne die Reihenfolge der verbleibenden Zeichen zu ändern. Die längste gemeinsame Teilfolge bedeutet die längste Teilfolge, die allen gegebenen Folgen gemeinsam ist.

In diesem Tutorial lernen Sie, die Länge der längsten gemeinsamen Teilsequenz zwischen zwei Sequenzen in Python zu finden.

Verwenden Sie die naive Methode, um die längste gemeinsame Teilsequenz in Python zu finden

Stellen Sie sich vor, wir haben zwei Sequenzen: S1 und S2, wobei:

S1 = QEREW

S2 = QWRE

Hier sind die gemeinsamen Untersequenzen QE, QW, QR, QRE und RE. Unter diesen ist die längste gemeinsame Teilsequenz QRE und hat eine Länge von 3.

Schauen wir uns nun die Python-Lösung an, um die Länge der längsten gemeinsamen Teilsequenz auszugeben.

Code:

def LCS(S1, S2, x, y):

    if x == 0 or y == 0:
        return 0

    if S1[x - 1] == S2[y - 1]:
        return LCS(S1, S2, x - 1, y - 1) + 1

    return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x - 1, y))


S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print("Length of LCS is", LCS(S1, S2, x, y))

Ausgang:

Length of LCS is 3

Diese Methode ist ein rekursiver Ansatz zur Lösung des LCS-Problems in Python. Es sucht nach allen möglichen Teilfolgen gegebener Folgen und findet die längste gemeinsame Teilfolge.

Verwenden Sie die dynamische Programmierung, um die längste gemeinsame Teilsequenz in Python zu finden

Die dynamische Programmierung ist die Optimierung des einfachen Rekursionsverfahrens. Wie wir sehen können, gibt es beim rekursiven Ansatz überlappende Teilprobleme mit vielen wiederholten Funktionsaufrufen.

Der dynamische Ansatz speichert das Ergebnis jedes Funktionsaufrufs in einem Array, sodass es bei Bedarf verwendet werden kann. Dadurch wird die Anzahl der Funktionsaufrufe reduziert.

Code:

def LCS(S1, S2, m, n):
    R = [[None] * (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:
                R[i][j] = 0
            elif S1[i - 1] == S2[j - 1]:
                R[i][j] = R[i - 1][j - 1] + 1
            else:
                R[i][j] = max(R[i - 1][j], R[i][j - 1])

    return R[m][n]


S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is", LCS(S1, S2, m, n))

Ausgang:

Length of LCS is 3

Diese Methode ist schneller und effizienter, da sie die Zeitkomplexität von O(mn) hat.