Längster gemeinsamer Teilstring in Python

Namita Chaudhary 10 Oktober 2023
  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
Längster gemeinsamer Teilstring in Python

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.

  • Wir werden alle Teilstrings des ersten Strings finden.
  • Wir prüfen, ob der aktuelle Teilstring des ersten Strings auch ein Teilstring des zweiten Strings ist.
  • Wenn beide Teilstrings übereinstimmen, speichern wir ihre Längen in einer bestimmten Variablen und aktualisieren diese Variable weiter.
  • Schließlich enthält die Variable, die die Länge des Teilstrings speichert, unser gewünschtes Ergebnis und wird gedruckt.

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.

  • Bei dem gegebenen Problem, den längsten gemeinsamen Teilstring zu finden, kann die kleinstmögliche Eingabe ein String der Länge 0 sein. Daher würde der Basisfall prüfen, ob eine der Längen der Eingaben 0 ist, dann sollte die Funktion eine 0 zurückgeben.
  • Jetzt werden wir die letzten Zeichen beider Zeichenketten vergleichen, dann treten zwei Fälle auf, in denen entweder beide Zeichen übereinstimmen würden oder sie nicht miteinander übereinstimmen würden.
  • Wenn das letzte Zeichen jeder der angegebenen Zeichenfolgen übereinstimmt, sollten wir die restlichen Zeichenfolgen rekursiv aufrufen. Daher reduzieren wir die Länge beider Saiten um 1 und addieren eins dazu, um die Länge der Saite zu zählen.
  • Wenn die Zeichen jedoch nicht übereinstimmen, erfolgt ein rekursiver Aufruf an die erste Zeichenfolge, deren Länge um 1 verringert wird, und dann an die zweite Zeichenfolge, um ihre Länge um 1 zu verringern.
  • Als Ergebnis wird die Länge genommen, das Maximum zwischen den beiden Aufrufen.

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.

  • Initialisieren Sie zunächst die erste Spalte und die erste Zeile der Tabelle. Diese Zellen werden mit dem Wert 0 initialisiert, wie wir in der Grundbedingung in Rekursion gesehen haben.
  • Wir verwenden Schleifen anstelle von rekursiven Aufrufen für unsere Logik.
  • Innerhalb der Schleifen, wenn das letzte Zeichen beider Strings übereinstimmt, erhöhen wir die Länge der jeweiligen Zelle um 1.
  • Andernfalls speichern wir die maximale Länge bis zur angrenzenden Zeile und Spalte in der jeweiligen Zelle.
  • Schließlich wird unser Ergebnis an der letzten Position der Tabelle gespeichert; deshalb geben wir dp[m][n] zurück.

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.

Verwandter Artikel - Python String