Langste gemeenschappelijke vervolgreeks: Python, C++ Voorbeeld

Wat is de langste gemeenschappelijke deelreeks?

De langste gemeenschappelijke subreeks (LCS) houdt in dat je twee tekenreeksen, patronen of reeksen objecten krijgt. Je moet binnen deze twee reeksen of tekenreeksen de langste subreeks vinden van elementen die in dezelfde volgorde voorkomen in beide tekenreeksen of patronen.

Voorbeeld

Stel, er zijn twee tekenreeksen beschikbaar. Laten we aannemen dat:

Patroon_1 = “RGBGARGA”
Patroon_2 = "BGRARG"

• Vanuit patroon_1 kunnen reeksen worden gegenereerd zoals “RGB”, “RGGA”, “RGAR”. Om een ​​reeks te creëren, moet je de relatieve positie van elk teken in de tekenreeks behouden.
• Vanuit patroon_2 kunnen we sequenties produceren zoals "BGR", "BRAG", "RARG". Sequenties kunnen worden geproduceerd zolang ze de relatieve positie van de oorspronkelijke tekenreeks behouden.

De term relatieve positie betekent orde.

Bijvoorbeeld, "BRG" is een geldige reeks omdat "B" eerst voorkomt, dan "R" en dan "G" in de oorspronkelijke tekenreeks pattern_2. Als een reeks echter "RBRG" is, is deze niet geldig, omdat in de oorspronkelijke tekenreeks (pattern_2) "B" eerst komt.

We hebben twee opties om de langste gemeenschappelijke deelreeks uit de gegeven twee reeksen of arrays te vinden.

• Naïeve methode
• Dynamische programmeeroplossing: de langste gemeenschappelijke vervolgreeks wordt ook wel LCS genoemd.

Een naïeve oplossing heeft een hogere tijdscomplexiteit en is niet de optimale oplossing. Door gebruik te maken van dynamische programmering (DP) overwinnen we dit complexiteitsprobleem.

Naïeve methode

De naïeve methode is een eenvoudige aanpak van het probleem, ongeacht de tijdscomplexiteit en andere optimalisatiefactoren. Deze methode bestaat in de meeste gevallen uit "brute force", meerdere lussen en recursieve aanroepen. De term "brute force" betekent dat alle mogelijke patronen voor een gegeven probleem worden doorlopen.

Voorbeeld

Laten we, uitgaande van het bovenstaande voorbeeld van patroon1 en patroon2, aannemen dat patroon1 een lengte heeft van m en dat patroon2 een lengte heeft van n. Om elk mogelijk geval te controleren, moeten we elke mogelijke deelreeks van patroon1 evalueren met patroon2.

Hier is een eenvoudige tekenreeks van 4 letters: "ABCD". We moeten bijvoorbeeld een reeks maken van "ABCD". We kunnen een teken wel of niet gebruiken. Dat betekent dat we voor elk teken twee keuzes hebben:

• Het personage wordt aan de vervolgreeks toegevoegd.
• Het teken wordt niet aan de vervolgreeks toegevoegd.

Hier tonen de afbeeldingen alle reeksen die we kunnen maken uit de reeks "ABCD".

Reeks met 1 teken:

Reeksen met 2 karakters:

Reeksen met 3 karakters:

Uit het bovenstaande diagram blijkt dat er 14 reeksen zijn. Als we geen letters nemen, in feite een lege reeks, dan zijn er in totaal 15 reeksen. Bovendien is de reeks "ABCD" zelf een reeks. Dus in totaal zijn er 16 reeksen.

Het is dus mogelijk om 2^4 of 16 deelreeksen te genereren uit "ABCD". Vervolgens een tekenreeks met een lengte van m zal een totale deelreeks van 2^m hebben.

Voor elke subreeks moeten we controleren of deze het hele patroon2 volgt. Dit kost O(n) tijd. O(n) staat voor de complexiteitsfunctie die de benodigde uitvoeringstijd berekent.

De totale tijdscomplexiteit wordt dus O(n*2^m). In het bovenstaande voorbeeld is de waarde van m=8 en n=5.

Hier zijn de stappen van de naïeve methode:

Stap 1) Neem een ​​reeks uit patroon1.
Stap 2) Combineer de reeks uit stap 1 met patroon 2.
Stap 3) Als dit overeenkomt, slaat u de deelreeks op.
Stap 4) Als er nog sequenties over zijn in patroon1, ga dan terug naar stap 1.
Stap 5) Druk de langste deelreeks af.

Optimale onderbouw

De term optimale substructuur betekent dat een optimale oplossing kan worden gevonden door de subproblemen op te lossen. In het bovenstaande voorbeeld hebben we bijvoorbeeld patroon1 en patroon2.

Stap 1) Neem de eerste twee tekens van elk patroon.

Stap 2) Neem van elk patroon het derde tot en met het vijfde karakter.

Stap 3) Ga op dezelfde manier verder met de overige tekens.

Recursieve structuur van het LCS-probleem

We bepalen de LCS (Long Common Sign) van de substring (een string die is gegenereerd uit een originele string). Vervolgens registreren we de lengte van de LCS van de substrings.

Hier is nog een interessante eigenschap overlappenping deelproblemenEr wordt gezegd dat een probleem overlap vertoont.ping deelproblemen als de probleemstelling kan worden opgedeeld in kleinere deelproblemen die meerdere keren in het programma kunnen worden gebruikt.

Het onderstaande diagram laat zien dat het recursieve algoritme de functie met dezelfde parameter meerdere keren heeft aangeroepen.

Kijk bijvoorbeeld naar de recursieboom. In het donkergekleurde vak zie je overlappingen.ping deelproblemen. (“RG”, “RA”), (“RG”, “R”) en andere worden meerdere keren aangeroepen.

Om dit te optimaliseren, hanteren we de volgende aanpak: Dynamisch programmeren (DP).

Recursieve methode van de langste gemeenschappelijke subreeks

De bovenstaande grafiek toont de recursieve methode. Elke recursieve functie heeft een basisgeval om de recursie te doorbreken of om terug te keren van de stack.

Voor deze implementatie gebruiken we een basisgeval. Dus, de algoritme is als volgt:

• Als alle elementen vóór het laatste element overeenkomen, verhoog dan de lengte met één en retourneer.
• Geef twee patronen door aan de functie en neem de maximale waarde van het resultaat.
• Als één patroon een lengte nul heeft, hebben we geen deelreeks om te vergelijken. Retourneert in dit geval 0. Dit is het basisscenario van de recursie.

Pseudo Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

implementatie in C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Output:

Length of LCS is: 5

implementatie in Python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
        return 0
    if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
        return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
    else:
        return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2),
                   lcs(pattern_1, pattern_2, len_1, len_2 - 1))

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Output:

Length of LCS is:  5

Dynamische programmeermethode voor de langste gemeenschappelijke subreeks (LCS)

Dynamisch programmeren betekent het optimaliseren van de eenvoudige recursieve methode. Als we bijvoorbeeld naar de grafiek van de recursieve of naïeve aanpak kijken, zien we dat er meerdere identieke functieaanroepen zijn. De methode van dynamisch programmeren slaat al deze berekeningen op in een array en hergebruikt ze wanneer nodig.

We gebruiken een 2D-array met afmetingen m x n, waarbij m en n de lengtes van patroon1 en patroon2 zijn. Voor een 2D-reeksWe kunnen List-datastructuren gebruiken in Python of vector-/array-datastructuren in C++.

Pseudo Code voor LCS met behulp van DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
    n = length of pattern_2 + 1
    dp[n][m]
    for i in range 0 to n + 1:
        for j in range 0 to m + 1:
            if i or j equals to 0:
                dp[i][j] = 0
            else if pattern_1[i] == pattern_2[j]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

Hier is de LCS-tabel die als 2D-arraydatastructuur wordt gebruikt voor de dynamische programmeerbenadering.

Laten we de logica die we hier hebben gebruikt eens toelichten. De stappen zijn:

Stap 1) Als i of j nul is, nemen we een lege string uit de twee gegeven strings en proberen we de gemeenschappelijke deelreeksen te vinden. Omdat de deelreeks die we nemen echter leeg is, is de lengte van de deelreeks 0.

Stap 2) Als twee tekens overeenkomen, kennen we de waarde toe aan de index (i,j) door de eerder berekende LCS, die zich in de index (i-1,j-1) bevindt (uit de vorige rij), te verhogen.

Stap 3) Als er geen overeenkomst is, nemen we de grootste LCS (Least Common Significant) van de twee aangrenzende indexen. Op deze manier moeten we alle waarden in de 2D-array invullen.

Stap 4) Ten slotte zullen we de waarde van de laatste cel van de 2D-array retourneren.

In principe bevatten alle waarden in de 2D-array de lengte van gemeenschappelijke subreeksen. De laatste cel bevat de lengte van de langste gemeenschappelijke subreeks.

implementatie in C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[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[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Output:

Length of LCS: 5

implementatie in Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
    n = len(pattern_2)
    # dp will store solutions as the iteration goes on
    dp = [[None] * (n + 1) for item in range(m + 1)]
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif pattern_1[i - 1] == pattern_2[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]

pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Output:

Length of LCS: 5

Beide snaren hebben dus de langste gemeenschappelijke deelreeks van lengte 5.

Kort gezegd berekenen we bij de dynamische programmeermethode (DP) elke taak slechts één keer. Bij de recursieve methode kan er overlap optreden.ping deelproblemen.

In dit dynamische programmeeralgoritme gebruiken we een 2D-matrix. Er worden twee strings gegeven (neem aan dat beide lengte n hebben). De benodigde ruimte in de array is dan nx n. Als de tekenreeksen groot genoeg zijn, hebben we een voor geheugen geoptimaliseerde versie van de DP-oplossing nodig.

De vereenvoudigde logica die in de code is gebruikt, is:

• Declareer een 2D-array DP[m][n].
• Vul de eerste rij en eerste kolom van de DP-array met 0.
• Neem i en j voor de iteratie.
• Als patroon1[i] gelijk is aan patroon2[j], dan update DP[i][j] = DP[i-1][j-1] + 1.
• Als pattern1[i] niet gelijk is aan pattern2[j], dan is DP[i][j] de maximale waarde tussen DP[i-1][j] en DP[i][j-1].
• Ga door totdat i en j m en n bereiken.
• Het laatste element, DP[m-1][n-1], zal de lengte bevatten.

Hier wordt het aangeduid als DP[m-1][n-1] omdat de array-index begint bij 0.

Veelgestelde vragen