Längsta vanliga följdsekvens: Python, C++ Exempelvis

Vad är den längsta vanliga följden?

Längsta gemensamma delsekvens (LCS) innebär att du får två strängar, mönster eller sekvenser av objekt. Bland dessa två sekvenser eller strängar måste du hitta den längsta delsekvensen av element i samma ordning som finns i båda strängarna eller mönstren.

Exempelvis

Till exempel finns det två strängar. Låt oss anta att:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Från pattern_1 kan sekvenser som "RGB", "RGGA", "RGAR" skapas. För att skapa en sekvens måste du bibehålla den relativa positionen för varje tecken i strängen.
• Från pattern_2 kan vi producera sekvenser som "BGR", "BRAG", "RARG". Sekvenser kan produceras så länge de bibehåller den ursprungliga strängens relativa position.

Termen relativ position betyder ordning.

Till exempel är ”BRG” en giltig sekvens eftersom ”B” dök upp först, sedan ”R” och sedan ”G” i den ursprungliga strängen pattern_2. Men om en sekvens är ”RBRG” är den inte giltig, eftersom ”B” kommer först i den ursprungliga strängen (pattern_2).

Vi har två alternativ för att hitta den längsta vanliga undersekvensen från de givna två sekvenserna eller arrayerna.

• Naiv metod
• Dynamisk programmeringslösning: Längsta vanliga delsekvensen kallas även LCS.

En naiv lösning har större tidskomplexitet och är inte den optimala lösningen. Med hjälp av dynamisk programmeringslösning (DP) övervinner vi komplexitetsproblemet.

Naiv metod

Den naiva metoden är en enkel metod för att lösa problemet, oavsett tidskomplexitet och andra optimeringsfaktorer. Den består av "brute force", flera loopar och rekursiva anrop i de flesta fall. Termen brute force betyder att man går igenom alla möjliga mönster för ett givet problem.

Exempelvis

Från ovanstående exempel på mönster1 och mönster2, låt oss anta att mönster1 har längden m och mönster2 har längden n. För att kontrollera alla möjliga fall måste vi utvärdera alla möjliga följder av mönster1 med mönster2.

Här är en enkel sträng med fyra bokstäver, ”ABCD”. Till exempel behöver vi skapa en sekvens från ”ABCD”. Antingen kan vi ta ett tecken eller inte. Det betyder att vi för varje tecken har två val:

• Tecknet kommer att läggas till i efterföljden.
• Tecknet kommer inte att läggas till i efterföljden.

Här visar bilderna alla sekvenser som vi kan göra från strängen "ABCD".

Sekvens med 1 tecken:

Sekvenser med 2 tecken:

Sekvenser med 3 tecken:

Enligt diagrammet ovan finns det 14 sekvenser. Om vi ​​inte tar några bokstäver, i princip en tom sträng, blir det totala antalet sekvenser 15. Dessutom är själva strängen "ABCD" en sekvens. Så det totala antalet sekvenser är 16.

Så det är möjligt att generera 2^4 eller 16 delsekvenser från "ABCD". Sedan skapas en sträng med en längd på m kommer att ha en total delsekvens på 2^m.

För varje delsekvens behöver vi kontrollera den för hela mönstret2. Det tar O(n) tid. O(n) är komplexitetsfunktionen som beräknar tiden det tar för exekvering.

Så total tidskomplexitet blir O(n*2^m). För exemplet vi har sett ovan är värdet på m=8 och n=5.

Här är stegen i den naiva metoden:

Steg 1) Ta en sekvens från mönster1.
Steg 2) Matcha sekvensen från steg 1 med mönster 2.
Steg 3) Om det matchar, spara sedan undersekvensen.
Steg 4) Om fler sekvenser finns kvar i mönster 1, gå sedan till steg 1 igen.
Steg 5) Skriv ut den längsta efterföljden.

Optimal underlag

Termen optimal delstruktur betyder att en optimal lösning kan hittas genom att lösa delproblemen. Till exempel, i exemplet ovan har vi mönster1 och mönster2.

Steg 1) Ta de två första tecknen från varje mönster.

Steg 2) Ta det tredje till femte tecknet från varje mönster.

Steg 3) Fortsätt på samma sätt med de återstående tecknen.

Rekursiv struktur för LCS-problem

Vi hittar LCS på delsträngen (en sträng genererad från en originalsträng). Sedan registrerar vi längden på LCS för delsträngarna.

Nu, här är en annan intressant egenskap överlappningping delproblemEtt problem sägs ha överlappningping delproblem om problemformuleringen kan delas upp i små delproblem och användas flera gånger i programmet.

Diagrammet nedan visar att den rekursiva algoritmen anropade funktionen med samma parameter flera gånger.

Titta till exempel på rekursionsträdet. I den mörka rutan kan du se överlappningping delproblem. (”RG”, ”RA”), (”RG”, ”R”) och andra anropas flera gånger.

För att optimera detta har vi tillvägagångssättet att Dynamisk programmering (DP).

Rekursiv metod för längsta gemensamma delföljd

Grafen som visas ovan är den rekursiva metoden. Varje rekursiv funktion har ett basfall för att bryta rekursionen eller börja återgå från sin stack.

För denna implementering kommer vi att använda ett basfall. Så, algoritm är som följande:

• Om alla element före det sista elementet har en matchning, öka längden med ett och returnera.
• Skicka två mönster till funktionen och ta maxvärdet av returvärdet.
• Om ett mönster har noll längd, så har vi ingen följd att jämföra. Returnera 0 i detta fall. Detta är basfallet för rekursionen.

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

Genomförande 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;
}

Produktion:

Length of LCS is: 5

Genomförande 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)))

Produktion:

Length of LCS is:  5

Dynamisk programmeringsmetod för längsta gemensamma delsekvens (LCS)

Dynamisk programmering innebär att optimera den rekursiva metoden. Om vi ​​till exempel tittar på grafen för rekursiva eller naiva metoder kan vi se att det finns flera identiska funktionsanrop. Den dynamiska programmeringsmetoden registrerar alla beräkningar i en array och återanvänder dem vid behov.

Vi kommer att använda en 2D-matris med dimensionerna mxn, där m och n är längderna på mönster1 och mönster2. För en 2D-array, kan vi använda List-datastrukturer i Python eller vektor-/matrisdatastrukturer i C++.

Pseudo Code för LCS med 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]

Här är tabellen LCS som används som en 2D-matrisdatastruktur för den dynamiska programmeringsmetoden.

Låt oss diskutera logiken vi använde här. Stegen är:

Steg 1) Om i eller j är noll, tar vi en tom sträng från de givna två strängarna och försöker hitta de gemensamma delsekvenserna. Men eftersom delsträngen vi tar är tom, är delsekvensens längd 0.

Steg 2) Om två tecken matchar, tilldelar vi värdet till (i,j)-indexet genom att öka den tidigare beräknade LCS, som finns i (i-1,j-1)-indexet (från föregående rad).

Steg 3) Om det inte matchar tar vi den maximala LCS-gränsen för de två intilliggande indexen. Och på så sätt behöver vi fylla alla värden i 2D-matrisen.

Steg 4) Slutligen kommer vi att returnera värdet för den sista cellen i 2D-matrisen.

I grund och botten innehåller alla värden i 2D-matrisen längden på gemensamma delsekvenser. Bland dessa innehåller den sista cellen längden på den längsta gemensamma delsekvensen.

Genomförande 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;
}

Produktion:

Length of LCS: 5

Genomförande 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))

Produktion:

Length of LCS: 5

Så båda strängarna har den längsta gemensamma följden av längd 5.

Kort sagt beräknar vi helt enkelt varje uppgift en gång i DP-metoden. I den rekursiva metoden kan vi ha överlappningping delproblem.

I denna dynamiska programmeringsalgoritm använder vi en 2D-matris. Det kommer att finnas två strängar (antag att båda har längden n). Då är utrymmet som behövs i arrayen nx n. Om strängarna är tillräckligt stora behöver vi en minnesoptimerad version av DP-lösningen.

Den förenklade logiken som togs i koden är:

• Deklarera en 2D Array DP[m][n].
• Fyll den första raden och den första kolumnen i DP-matrisen med 0.
• Ta i och j för iterationen.
• Om mönster1[i] är lika med mönster2[j], uppdatera då DP[i][j] = DP[i-1][j-1] + 1.
• Om mönster1[i] inte är lika med mönster2[j], så kommer DP[i][j] att vara det maximala värdet mellan DP[i-1][j] och DP[i][j-1].
• Fortsätt tills i och j når m och n.
• Det sista elementet, DP[m-1][n-1], kommer att innehålla längden.

Här adresseras den som DP[m-1][n-1] eftersom arrayindexet börjar från 0.

Vanliga frågor