Längster gemeinsamer Teilstring in Python

1. Längster gemeinsamer Teilstring in Python
2. Längster gemeinsamer Teilstring mit Schleifen in Python
3. Verwendung der Rekursion zur Ermittlung der längsten gemeinsamen Zeichenfolge
4. Dynamische Programmierung, um die längste gemeinsame Teilzeichenkette in Python zu finden
5. Fazit

String in Python speichert eine Folge von Zeichen darin, um verschiedene Operationen mit ihnen auszuführen. Teilstrings sind ein Teil dieser Strings.

In diesem Artikel müssen wir den längsten gemeinsamen Teilstring zwischen zwei gegebenen Strings finden und werden verschiedene Lösungen dafür diskutieren.

Längster gemeinsamer Teilstring in Python

Ein Teilstring ist eine fortlaufende Folge von Zeichen innerhalb eines gegebenen Strings. Es kann beliebig lang sein.

Das Hauptproblem besteht darin, dass uns zwei Zeichenfolgen zur Verfügung gestellt wurden und wir eine Teilzeichenfolge finden müssen, die zwischen den angegebenen Zeichenfolgen gemeinsam ist und die längste aller möglichen gemeinsamen Teilzeichenfolgen sein sollte.

Input: str1 = "HaveAAppleRegularly"
       str2 = "HaveAnAnApple"
Output: "Apple"

Im obigen Beispiel haben wir zwei gemeinsame Teilstrings zwischen den gegebenen Strings, "Have" und "Apple". Aber da die Länge des Teilstrings "Apple" der längste unter den restlichen Teilstrings ist; daher wird es als unser Ergebnis angezeigt.

Dieses Problem kann mit verschiedenen Konzepten wie Rekursion und dynamischer Programmierung gelöst werden.

Längster gemeinsamer Teilstring mit Schleifen in Python

Schleifen können verwendet werden, um einen String zu durchlaufen. Wir können hier mit den Schleifen durch die Zeichenfolge iterieren und unsere längste gemeinsame Teilzeichenfolge zwischen den beiden angegebenen Zeichenfolgen finden.

Wir werden bei diesem Ansatz sowohl for- als auch while-Schleifen verwenden. Im Folgenden sind die Schritte aufgeführt, die befolgt werden müssen, um die längste gemeinsame Teilzeichenfolge in Python zu finden.

Codebeispiel:

str1 = "PokemonGo"
str2 = "StopPokemonLetsGo"
result = 0
for i in range(len(str1)):
    for j in range(len(str2)):
        k = 0
        while (
            (i + k) < len(str1) and (j + k) < len(str2) and str1[i + k] == str2[j + k]
        ):
            k = k + 1
        result = max(result, k)

print("Length of the longest common substring is:", result)

Ausgabe:

Length of the longest common substring is: 7

Alle Teilstrings des Strings können in O(n^2)-Zeit berechnet werden, während die Überprüfung, ob der aktuelle Teilstring mit einem Teilstring des zweiten Strings übereinstimmt, O(m)-Zeit in Anspruch nehmen würde. Die Zeitkomplexität für den obigen Ansatz wäre O(n^2 * m), wobei n und m die Längen der beiden gegebenen Strings sind.

Da wir jedoch keinen zusätzlichen Raum genommen haben, um die Lösung zu erreichen, wäre die Raumkomplexität für die obige Lösung O(1).

Verwendung der Rekursion zur Ermittlung der längsten gemeinsamen Zeichenfolge

Rekursion bezieht sich auf eine Funktion, die sich selbst aufruft. Wir brauchen einen Basisfall und das Auswahldiagramm für das vorliegende Problem in Rekursion.

Wir werden die folgenden Schritte ausführen, um die längste gemeinsame Teilzeichenfolge in Python zu finden.

Codebeispiel:

def LCS(s1, s2, n, m):
    if n == 0 or m == 0:
        return 0

    if s1[n - 1] == s2[m - 1]:
        return 1 + lcs(s1, s2, n - 1, m - 1)

    else:
        return max(lcs(s1, s2, n, m - 1), lcs(s1, s2, n - 1, m))


s1 = "pokemonGo"
s2 = "watchPokemon"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)

Ausgabe:

Length of the longest common substring is: 7

Die Zeitkomplexität der obigen Lösung wäre O(3^(m+n)), und die Raumkomplexität wäre O(m+n).

Dynamische Programmierung, um die längste gemeinsame Teilzeichenkette in Python zu finden

Die Grundidee der dynamischen Programmierung besteht darin, die Längen für alle Teilstrings beider Strings zu finden und ihre jeweiligen Längen in einer Tabelle zu speichern. Da die Rekursion verwendet wird, besteht die Möglichkeit, dass ein Stapelüberlauffehler auftritt, da der Rekursionsstapel bei großen Eingaben weiter zunimmt.

Wir stellen das Konzept der dynamischen Programmierung vor, bei der wir eine Tabelle bilden und die Ergebnisse für die jeweiligen Teilstrings weiter speichern. Derselbe Algorithmus, den wir bei der Rekursion verwendet haben, wird auch mit einigen Änderungen verwendet.

Nun besprechen wir die Schritte zum Finden der längsten gemeinsamen Teilzeichenfolge in Python.

Codebeispiel:

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

    dp = [[0 for x in range(m + 1)] for y in range(n + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]


s1 = "playbatball"
s2 = "batballwicket"
n = len(s1)
m = len(s2)
res = lcs(s1, s2, n, m)
print("Length of the longest common substring is:", res)

Ausgabe:

Length of the longest common substring is: 7

Da es in unserer Lösung nur zwei Schleifen gibt, wäre die Zeitkomplexität für obige Lösung O(m*n). Wir verwenden zusätzlichen Platz, indem wir eine Tabelle bilden, um die Ergebnisse zu speichern.

Die Raumkomplexität der obigen Lösung wäre O(m*n).

Fazit

Wir haben drei verschiedene Ansätze kennengelernt, um den längsten gemeinsamen Teilstring zwischen zwei gegebenen Strings zu finden. Der erste Ansatz, ein naiver Ansatz, verwendet drei Schleifen und findet alle Teilstrings des gegebenen Strings und überprüft den längsten aller Teilstrings.

Der zweite Ansatz verwendet Rekursion, während der dritte Ansatz dynamische Programmierung verwendet, um die längste gemeinsame Teilzeichenfolge in Python zu finden. Der dritte Ansatz wäre der schnellste aller in diesem Artikel diskutierten Lösungen zur Lösung des Problems und sollte bevorzugt werden.