Længste fælles efterfølger: Python, C++ Eksempel

Hvad er den længste fælles efterfølger?

Længste fælles delsekvens (LCS) betyder, at du får to strenge, mønstre eller sekvenser af objekter. Blandt disse to sekvenser eller strenge skal du finde den længste delsekvens af elementer i samme rækkefølge, der findes i begge strenge eller mønstre.

Eksempel

For eksempel er der angivet to strenge. Lad os antage, at:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Fra pattern_1 kan sekvenser som "RGB", "RGGA" og "RGAR" produceres. For at oprette en sekvens skal du bevare den relative position af hvert tegn i strengen.
• Fra pattern_2 kan vi producere sekvenser som "BGR", "BRAG", "RARG". Sekvenser kan produceres, så længe de bevarer den oprindelige strengs relative position.

Udtrykket relativ position betyder orden.

For eksempel er "BRG" en gyldig sekvens, fordi "B" optrådte først, derefter "R" og derefter "G" i den oprindelige streng pattern_2. Men hvis en sekvens er "RBRG", er den ikke gyldig, fordi "B" kommer først i den oprindelige streng (pattern_2).

Vi har to muligheder for at finde den længste fælles undersekvens fra de givne to sekvenser eller arrays.

• Naiv metode
• Dynamisk programmeringsløsning: Længste fælles undersekvens er også kendt som LCS.

En naiv løsning har større tidskompleksitet og er ikke den optimale løsning. Ved at bruge den dynamiske programmeringsløsning (DP) overvinder vi kompleksitetsproblemet.

Naiv metode

Den naive metode er en simpel tilgang til problemet, uanset tidskompleksitet og andre optimeringsfaktorer. Den består af "brute force", flere løkker og rekursive kald i de fleste tilfælde. Udtrykket brute force betyder at gennemgå alle mulige mønstre for et givet problem.

Eksempel

Fra ovenstående eksempel på mønster1 og mønster2, lad os antage, at mønster1 har en længde på m og mønster2 har en længde på n. For at kontrollere alle mulige tilfælde er vi nødt til at evaluere alle mulige efterfølger af mønster1 med mønster2.

Her er en simpel streng på 4 bogstaver, "ABCD". For eksempel skal vi oprette en sekvens ud fra "ABCD". Enten kan vi tage et tegn eller ej. Det betyder, at vi for hvert tegn har to valgmuligheder:

• Tegnet vil blive tilføjet til efterfølgen.
• Tegnet vil ikke blive tilføjet til efterfølgen.

Her viser billederne alle de sekvenser, vi kan lave fra strengen "ABCD".

Sekvens med 1 tegn:

Sekvenser med 2 tegn:

Sekvenser med 3 tegn:

Fra ovenstående diagram er der 14 sekvenser. Hvis vi ikke tager nogen bogstaver, dybest set en tom streng, vil det samlede antal sekvenser være 15. Desuden er strengen "ABCD" i sig selv en sekvens. Så det samlede antal sekvenser er 16.

Så det er muligt at generere 2^4 eller 16 delsekvenser fra "ABCD". Derefter en streng med en længde på m vil have en samlet delsekvens på 2^m.

For hver delsekvens skal vi kontrollere den for hele mønsteret2. Det vil tage O(n) tid. O(n) står for den kompleksitetsfunktion, der beregner den tid, det tager at udføre den.

Så den samlede tidskompleksitet bliver O(n*2^m). For det eksempel vi har set ovenfor, er værdien af ​​m=8 og n=5.

Her er trinene i den naive metode:

Trin 1) Tag en sekvens fra mønster1.
Trin 2) Match rækkefølgen fra trin 1 med mønster 2.
Trin 3) Hvis det matcher, skal du gemme efterfølgen.
Trin 4) Hvis der er flere sekvenser tilbage i mønster1, skal du gå til trin 1 igen.
Trin 5) Udskriv den længste sekvens.

Optimal underbygning

Udtrykket optimal understruktur betyder, at en optimal løsning kan findes ved at løse underproblemerne. For eksempel har vi i ovenstående eksempel mønster1 og mønster2.

Trin 1) Tag de første to tegn fra hvert mønster.

Trin 2) Tag det tredje til femte tegn fra hvert mønster.

Trin 3) Fortsæt på samme måde med de resterende tegn.

Rekursiv struktur af LCS-problem

Vi finder LCS'en på delstrengen (en streng genereret fra en original streng). Derefter registrerer vi længden af ​​LCS'en for delstrengene.

Her er en anden interessant egenskab overlapningping delproblemerEt problem siges at have overlapping delproblemer, hvis problemformuleringen kan opdeles i små delproblemer og bruges flere gange i programmet.

Diagrammet nedenfor viser, at den rekursive algoritme kaldte funktionen med den samme parameter flere gange.

Se for eksempel på rekursionstræet. I den mørke boks kan du se overlapningping delproblemer. ("RG", "RA"), ("RG", "R") og andre kaldes flere gange.

For at optimere dette har vi fremgangsmåden Dynamisk programmering (DP).

Rekursiv metode til længste fælles følge

Grafen vist ovenfor er den rekursive metode. Hver rekursiv funktion har et basistilfælde for at bryde rekursionen eller begynde at returnere fra sin stak.

Til denne implementering vil vi bruge et basisscenarie. Så, algoritme er som følgende:

• Hvis alle elementer før det sidste element har et match, så forøg længden med én og returner.
• Send to mønstre til funktionen, og tag den maksimale værdi af returværdien.
• Hvis et mønster har nul længde, så har vi ingen efterfølger at sammenligne. Returner 0 i dette tilfælde. Dette er grundtilfældet af rekursionen.

Kaldenavn 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))

Gennemførelse i 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

Gennemførelse i 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

Dynamisk programmeringsmetode for længste fælles delsekvens (LCS)

Dynamisk programmering betyder optimering af den almindelige rekursive metode. Hvis vi for eksempel ser på grafen for den rekursive eller naive tilgang, kan vi se, at der er flere identiske funktionskald. Den dynamiske programmeringsmetod registrerer alle beregningerne i et array og genbruger dem, når det er nødvendigt.

Vi bruger et 2D-array med dimensionerne mxn, hvor m og n er længderne af mønster1 og mønster2. For et 2D-array, kan vi bruge List-datastrukturer i Python eller vektor/array-datastrukturer i C++.

Kaldenavn Code for LCS ved hjælp af 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]

Her er tabellen LCS, der bruges som en 2D array-datastruktur til den dynamiske programmeringstilgang.

Lad os diskutere den logik, vi brugte her. Trinene er:

Trin 1) Hvis i eller j er nul, tager vi en tom streng fra de givne to strenge og forsøger at finde de fælles delsekvenser. Men da den delstreng, vi tager, er tom, er delsekvensens længde 0.

Trin 2) Hvis to tegn matcher, tildeler vi værdien til (i,j)-indekset ved at øge den tidligere beregnede LCS, som findes i (i-1,j-1)-indekset (fra den forrige række).

Trin 3) Hvis det ikke stemmer overens, tager vi den maksimale LCS for de to tilstødende indekser. Og på denne måde skal vi udfylde alle værdierne i 2D-matrixen.

Trin 4) Til sidst returnerer vi værdien af ​​den sidste celle i 2D-arrayet.

Grundlæggende set indeholder alle værdier i 2D-matrixen længden af ​​fælles delsekvenser. Blandt disse indeholder den sidste celle længden af ​​den længste fælles delsekvens.

Gennemførelse i 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

Gennemførelse i 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

Så begge strenge har den længste fælles efterfølger af længde 5.

Kort sagt beregner vi blot hver opgave én gang i DP-metoden. I den rekursive metode kan vi have overlap.ping delproblemer.

I denne dynamiske programmeringsalgoritme bruger vi en 2D-matrix. Der vil være givet to strenge (antag at begge har længden n). Så er den nødvendige plads i arrayet nx n. Hvis strengene er store nok, skal vi bruge en hukommelsesoptimeret version af DP-løsningen.

Den forenklede logik, der blev taget i koden, er:

• Erklær en 2D Array DP[m][n].
• Udfyld den første række og første kolonne i DP-arrayet med 0.
• Tag i og j for iterationen.
• Hvis mønster1[i] er lig med mønster2[j], så opdater DP[i][j] = DP[i-1][j-1] + 1.
• Hvis mønster1[i] ikke er lig med mønster2[j], så vil DP[i][j] være den maksimale værdi mellem DP[i-1][j] og DP[i][j-1].
• Fortsæt indtil i og j når m og n.
• Det sidste element, DP[m-1][n-1], vil indeholde længden.

Her adresseres den som DP[m-1][n-1], fordi array-indekset starter fra 0.

Ofte Stillede Spørgsmål