Længste almindelige efterfølgende

I denne vejledning lærer du, hvordan den længste almindelige efterfølger findes. Du finder også arbejdseksempler på den længste almindelige efterfølgende i C, C ++, Java og Python.

Den længste fælles undersekvens (LCS) er defineret som den længste efterfølgende, der er fælles for alle de givne sekvenser, forudsat at elementerne i undersekvensen ikke kræves for at indtage på hinanden følgende positioner inden for de originale sekvenser.

Hvis S1 og S2 er de to givne sekvenser, er Z den fælles undersekvens af S1 og S2, hvis Z er en undersekvens af både S1 og S2. Desuden skal Z være en strengt stigende sekvens af indekserne for både S1 og S2.

I en strengt stigende sekvens skal indekserne for elementerne valgt fra de originale sekvenser være i stigende rækkefølge i Z.

Hvis

 S1 = (B, C, D, A, A, C, D)

Derefter (A, D, B)kan det ikke være en sekvens af S1, da rækkefølgen af ​​elementerne ikke er den samme (dvs. ikke strengt stigende sekvens).

Lad os forstå LCS med et eksempel.

Hvis

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Derefter er almindelige efterfølgende (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Blandt disse efterfølgende (C, D, A, C)er den længste almindelige efterfølgende. Vi vil finde denne længste almindelige efterfølgende anvendelse ved hjælp af dynamisk programmering.

Inden du fortsætter, skal du gennemgå dynamisk programmering, hvis du ikke allerede kender til dynamisk programmering.

Brug af dynamisk programmering til at finde LCS

Lad os tage to sekvenser:

Den første sekvens anden sekvens

Følgende trin følges for at finde den længste almindelige efterfølgende.

  1. Opret en dimensionstabel, n+1*m+1hvor n og m er længderne på henholdsvis X og Y. Den første række og den første kolonne er fyldt med nuller. Initialiser en tabel
  2. Udfyld hver celle i tabellen ved hjælp af følgende logik.
  3. Hvis tegnet, der svarer til den aktuelle række og den aktuelle kolonne, matcher, skal du udfylde den aktuelle celle ved at tilføje en til det diagonale element. Peg en pil mod den diagonale celle.
  4. Tag ellers den maksimale værdi fra den forrige kolonne og det foregående rækkeelement til udfyldning af den aktuelle celle. Peg en pil mod cellen med maksimal værdi. Hvis de er lige, skal du pege på nogen af ​​dem. Udfyld værdierne
  5. Trin 2 gentages, indtil tabellen er fyldt. Udfyld alle værdier
  6. Værdien i den sidste række og den sidste kolonne er længden af ​​den længste fælles efterfølgende. Nederste højre hjørne er længden af ​​LCS
  7. For at finde den længste fælles efterfølgende, start fra det sidste element og følg pilens retning. Elementerne, der svarer til symbolet (), danner den længste fælles efterfølgende. Opret en sti i henhold til pilene

Således er den længste almindelige efterfølgende CD.

LCS

Hvordan er en dynamisk programmeringsalgoritme mere effektiv end den rekursive algoritme, når man løser et LCS-problem?

Metoden til dynamisk programmering reducerer antallet af funktionsopkald. Det gemmer resultatet af hvert funktionsopkald, så det kan bruges i fremtidige opkald uden behov for overflødige opkald.

I den ovennævnte dynamiske algoritme lagres resultaterne fra hver sammenligning mellem elementerne i X og elementerne i Y i en tabel, så de kan bruges i fremtidige beregninger.

Så den tid, det tager med en dynamisk tilgang, er den tid, det tager at udfylde tabellen (dvs. O (mn)). Mens rekursionsalgoritmen har kompleksiteten på 2 max (m, n) .

Længste almindelige efterfølgende algoritme

 X og Y er to givne sekvenser Initialiser en tabel LCS af dimension X. længde * Y. længde X. label = X Y. label = Y LCS (0) () = 0 LCS () (0) = 0 Start fra LCS ( 1) (1) Sammenlign X (i) og Y (j) Hvis X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Peg en pil mod LCS (i) (j) Ellers LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Peg en pil mod max (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java og C / C ++ eksempler

Python Java C C ++ 
 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)
 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )
 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )
 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )

Længste almindelige efterfølgende applikationer

  1. i komprimering af genomdannelsesdata
  2. for at godkende brugere inden for deres mobiltelefon gennem in-air signaturer

Interessante artikler...